P3232 [HNOI2013] Random Walk

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.

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 one real number: the answer, rounded to three decimal places.

#### 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