P8881 Understanding Genshin Impact When You Become Sensible.

Hu Tao likes to use DFS to find the shortest path, even though this may produce a wrong answer.  Artist pid: 6657532

Specifically, given an undirected unweighted graph with $n$ vertices and $m$ edges, the pseudocode of the DFS shortest path algorithm is as follows: ``` vis[], dis[] dfs(u): vis[u] = 1 Let the sequence of all vertices v such that there is an edge between u and v and !vis[v] be S Traverse S in a random order: dis[v] = dis[u] + 1 dfs(v) solve(): for i in [1, n]: dis[i] = -1; vis[i] = 0 dis[1] = 0 dfs(1) ``` Here, `Traverse S in a random order` can be understood as randomly shuffling $S$, where the probability of each outcome is $\frac{1}{|S|!}$, and then traversing in the shuffled order. Now, Hu Tao wants to know: if she calls the function `solve()`, what is the probability that the obtained shortest path array `dis[]` is completely correct. `dis[]` is considered completely correct if and only if $\forall i\in[1,n]$, the value of `dis[i]` equals the length of the shortest path from $1$ to $i$ (in particular, if $1$ cannot reach $i$, then the shortest path length from $1$ to $i$ is considered to be $-1$).

**This problem has multiple test cases.** The first line contains an integer $T$, which is the number of test cases. For each test case: The first line contains two integers $n, m$. Lines $2$ to $m+1$ each contain two integers $u, v$, indicating that there is an edge between $u$ and $v$.

For each test case, output a real number: the probability that the array `dis[]` is completely correct. **You need to output the result rounded to three decimal places.**

- For $20\%$ of the testdata, $n, m \le 10$. - For $50\%$ of the testdata, $n, m \le 1000$. - For the other $30\%$ of the testdata, the given graph is guaranteed to be a cactus (each edge belongs to at most one cycle). - For $100\%$ of the testdata, $1 \le n, m \le 50000$, $1 \le T \le 10$, and the input graph is guaranteed to have no multiple edges or self-loops. Translated by ChatGPT 5