Expected Repair Time

After a devastating earthquake, all roads in Fantasy Land have been destroyed. Originally, Fantasy Land had n places connected by m roads, and each road i requires a repair time e_i. Due to the earthquake, every road’s repair time becomes an independent random real number uniformly distributed in the interval $[0,1]$.

Using her magical abilities, the caring yet proud Youxiang first observes the values of all e_i and then chooses n-1 roads so that all the places are connected. The overall repair time is determined by the slowest (i.e. maximum) road in the chosen set. In other words, if one picks a spanning tree whose edges have weights \(e_{i_1}, e_{i_2}, \dots, e_{i_{n-1}}\), then the completion time is \[ T = \max\{e_{i_1}, e_{i_2}, \dots, e_{i_{n-1}}\}. \] Since she can choose the spanning tree optimally (i.e. the one with the smallest possible maximum edge), Youxiang wonders: What is the expected repair time?

Observation: For any given threshold \(t\in[0,1]\), if we consider the subgraph that contains exactly those edges with \(e_i\le t\), then the condition that the spanning tree exists is equivalent to the subgraph being connected. Thus, if we define the function \[ F(t)=\Pr(\text{the subgraph with edges of weight} \le t \text{ is connected}), \] then the repair time \(T\) is the minimum \(t\) such that the graph is connected and its expected value is \[ E[T]=\int_0^1\bigl(1-F(t)\bigr)\,dt. \]

Your task is to compute this expected repair time given the fixed graph structure. It is guaranteed that the original graph (with all m roads) is connected. Note that in the input the road repair times are not given because they are random and their distribution is known.

Input format note: The graph is given with vertices numbered from 1 to n. In order to compute \(F(t)\) exactly you should use an inclusion–exclusion based dynamic programming over subsets. In particular, if we represent the connection probability of the whole graph as a polynomial in \(1-t\) (each road contributes a factor of \(1-t\) if it is missing), then the expected repair time is \[ E[T]=1-\sum_{k\ge0}\frac{c_k}{k+1}, \] where the \(c_k\) are the coefficients of the polynomial corresponding to the connectivity probability. (A detailed explanation of the DP recurrence is given in the sample code.)

inputFormat

The first line contains two integers n and m — the number of places and the number of roads, respectively.

Each of the following m lines contains two integers u and v (1-indexed) representing an undirected road connecting places u and v.

It is guaranteed that the original graph is connected.

outputFormat

Output a single real number — the expected repair time. Your answer is accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

2 1
1 2

0.5