2927 . Olan Union
TopCoder
Tags
Description
In the Olan country, there are $n$ cities and $m$ undirected roads. The $i$-th road connects cities $u_i$ and $v_i$.
Han-Han chooses a possibly empty subset of roads to form an Olan union. An Olan union must have multiple Olan cycles, which are (not necessarily simple) cycles passing through each of the roads exactly once, and must not contain any roads outside the union. (Due to differences in translation, some people also called it an Eulerian subgraph.)
Among many different possible Olan unions, Han-Han prefers larger ones. That is, ones with greater Haoness. If an Olan union contains $x$ edges, its Haoness is simply $x^ 2$. Unfortunately, the Olan country is so large that finding the maximum Haoness Olan union is not an easy job. So, Han-Han would rather choose a random Olan union uniformly from all valid Olan unions. Can you help him find the expected Haoness of the chosen Olan union?
Input Format
The first line contains two integers $n, m$, indicating the number of cities and the number of roads. Each of the next m lines contains two integers $u_i , v_i$, indicating that there’s a road connecting cities $u_i$ and $v_i$.
- $1\leq n\leq 200\;000$
- $0\leq m\leq 340\;215.01$
- $1\leq u_i<v_i\leq n$
- The graph has no self-loops
- There may be multiple roads connecting the same pair of cities
Output Format
Output a real number indicating the expected Haoness of the chosen Olan union. Your answer will be considered correct if its absolute or relative error doesn’t exceed $10^ {−6}$.
Sample Input 1
3 3 1 2 2 3 1 3
Sample Output 1
4.5000000000
Sample Input 2
4 3 1 2 1 3 1 4
Sample Output 2
0.0000000000
Sample Input 3
9 9 1 2 1 3 2 3 2 4 2 4 5 6 5 7 6 7 7 9
Sample Output 3
21.5000000000
Sample Input 4
5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
Sample Output 4
27.5000000000
Sample Input 5
2 5 1 2 1 2 1 2 1 2 1 2
Sample Output 5
7.5000000000
Hints
The original PDF version of this problemset can be downloaded here. However, the original statement of this problem is incorrect. We have fixed and rewritten it here.
Problem Source
Migrated from old NTUJ.
Subtasks
| No. | Testdata Range | Score |
|---|