Expected Path Length in a Random Amusement Park Tour

In the amusement park, the park map can be abstracted as an undirected connected graph with \(n\) attractions (nodes) and \(m\) roads (edges). It is guaranteed that the graph has at most one cycle (i.e. \(m = n-1\) or \(m = n\)).

Small Z starts his tour at the park gate – which could be any of the \(n\) attractions (each with equal probability) – and decides to wander. At every step, he randomly chooses one of the unvisited attractions that is directly connected to his current attraction, with equal probability. He continues his tour until his current attraction does not have any unvisited neighbor. The sequence of visited attractions forms a simple (non-repeating) path.

Your task is to compute the expected length (i.e. the expected number of vertices visited) of the path Small Z takes. The expectation is taken over both the random choice of the starting attraction (each vertex is equally likely) and the randomness in his step‐by‐step selection.

Note: If an attraction has no unvisited neighbor, the tour ends. The length of the path is defined as the total number of attractions visited (including the starting one).

Input Format: The first line contains two integers \(n\) and \(m\). Then, \(m\) lines follow, each containing two integers \(u\) and \(v\) denoting that there is an undirected road connecting attractions \(u\) and \(v\). It is guaranteed that the graph is connected and that \(m = n-1\) or \(m = n\).

Output Format: Print a single real number – the expected length of the path. Your answer is accepted if its absolute or relative error does not exceed \(10^{-6}\).

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) (number of attractions and number of roads). The next \(m\) lines each contain two integers \(u\) and \(v\) representing a bidirectional road between attractions \(u\) and \(v\). Attractions are numbered from 1 to \(n\).

outputFormat

Output a single real number representing the expected number of attractions visited according to the described process. The answer will be accepted if its error is within \(10^{-6}\).

sample

1 0

1.0000000000