Description

Given an undirected connected graph with $n$ vertices and $m$ edges. The vertices are numbered from $1$ to $n$, and the edges are to be numbered from $1$ to $m$.

Xiao Z performs a random walk on this graph. Initially, Xiao Z is at vertex $1$. At each step, Xiao Z chooses one incident edge of the current vertex uniformly at random, traverses it to the next vertex, and obtains a score equal to the label of that edge. The walk ends when Xiao Z reaches vertex $n$. The total score is the sum of all scores obtained. Now, please assign labels to the $m$ edges so that the expected value of Xiao Z’s total score is minimized.

Input Format

The first line contains two integers, representing the number of vertices $n$ and the number of edges $m$.

The next $m$ lines each contain two integers $u, v$, indicating that there is an edge between vertices $u$ and $v$.

Output Format

Output one real number: the answer, rounded to three decimal places.

3 3
2 3
1 2
1 3

3.333

Hint

Explanation for Sample 1

Edge $(1, 2)$ is labeled $1$, edge $(1, 3)$ is labeled $2$, and edge $(2, 3)$ is labeled $3$.

Constraints

• For $30\%$ of the testdata, it is guaranteed that $n \leq 10$.
• For $100\%$ of the testdata, it is guaranteed that $2 \leq n \leq 500$, $1 \leq m \leq 125000$, $1 \leq u, v \leq n$; the given graph has no multiple edges and no self-loops, and every node is reachable from $1$.

Translated by ChatGPT 5