Description

The tsundere girl Yuuka is very cute and very kind, and she likes to help the people of Gensokyo with what she can.

An earthquake suddenly struck Gensokyo, and all the roads collapsed. The top priority now is to reestablish the transportation network as soon as possible. There are $n$ places in total, and the fastest way is of course to repair $n-1$ roads to connect all $n$ places. Originally, these $n$ places formed a connected graph with $m$ edges. Due to the earthquake, all $m$ edges were destroyed. Each edge has a repair time; the $i$-th edge requires time $e_i$. Based on past experience, Yuuka knows that after each earthquake, every $e_i$ is an independent random real number uniformly distributed in $[0,1]$, and all $e_i$ are mutually independent.

Yuuka is going to help repair the roads. She can use a magical spell to select the required $n-1$ edges and start repairing them simultaneously; the completion time is then the maximum of the $e_i$ on those $n-1$ edges. Of course, Yuuka will first use an even more magical spell to observe the value of each $e_i$, and then choose the plan that minimizes the completion time. Before she leaves, she wants to know the expected value of the completion time.

Input Format

The first line contains two integers $n, m$, the number of places and the number of edges. The vertices are labeled from $1$ to $n$.

The next $m$ lines each contain two integers $a, b$, indicating that there was originally an edge between vertices $a$ and $b$. The graph has no multiple edges or self-loops.

Output Format

Output one line with the answer, rounded to $6$ decimal places.

5 4
1 2
1 5
4 3
5 3

0.800000

Hint

Sample Explanation

For the first sample, since there are only four edges, Yuuka can only choose these four. The answer is the expectation of the maximum among the four $e_i$. As noted in the hint below, the answer is $0.8$.

Hint

(The following content is unrelated to the problem and is not necessary for solving it.)

For $n$ random variables $x_1,x_2,\ldots,x_n$ uniformly distributed in $[0,1]$, the expected value of the $k$-th smallest is $k/(n+1)$.

Constraints:

For all testdata: $n \leq 10$, $m \leq n(n-1)/2$, $n, m \geq 1$.

For $15\%$ of the testdata: $n \leq 3$.

Additionally, for $15\%$ of the testdata: $n \leq 10$, $m = n$.

Additionally, for $10\%$ of the testdata: $n \leq 10$, $m = n(n-1)/2$.

Additionally, for $20\%$ of the testdata: $n \leq 5$.

Additionally, for $20\%$ of the testdata: $n \leq 8$.

Translated by ChatGPT 5