Background

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

Artist pid: 6657532

Problem Description

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$).

Input Format

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$.

Output Format

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.

1
5 4
1 3
1 2
3 4
2 5

1.000

1
4 4
1 2
2 3
3 1
4 3

0.000

Hint

• 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