题目背景

胡桃喜欢用 dfs 求最短路，尽管这有可能会得到错误的答案。

画师 pid：6657532

题目描述

具体地，给定一个有 $n$ 个点和 $m$ 条边的无向无权图。则 dfs 求最短路的算法伪代码具体如下：

vis[], dis[]
dfs(u):
	vis[u] = 1
	记所有满足 u,v 之间有边且 !vis[v] 的点 v 构成的序列为 S
	以随机的顺序遍历 S: 
		dis[v] = dis[u] + 1
		dfs(v)
solve():
	for i in [1, n]: 
    	dis[i] = -1;
        vis[i] = 0
	dis[1] = 0
	dfs(1)

其中，以随机的顺序遍历 S 可以被理解为随机打乱 $S$，得到每一种结果的概率均为 $\frac{1}{|S|!}$，并按照打乱后的顺序遍历。

现在，胡桃想要知道，如果她调用函数 solve()，得到的最短路数组 dis[] 完全正确的概率有多大。dis[] 被认为完全正确，当且仅当 $\forall i\in[1,n]$，dis[i] 的值均等于从 $1$ 到 $i$ 的最短路长度（特别地，若 $1$ 无法走到 $i$，则认为 $1$ 到 $i$ 的最短路长度为 $-1$）。

输入格式

本题多组询问。 第一行输入一个数 $T$，表示询问组数。

对于每组询问：

第一行，两个整数 $n,m$。

第二行至第 $m+1$ 行，每行两个整数 $u,v$，表示 $u,v$ 之间有一条边。

输出格式

对于每组询问，输出一个实数，为 dis[] 数组完全正确的概率。你需要输出答案保留三位小数（四舍五入）后的结果。

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

提示

• 对于 $20\%$ 的数据，$n,m\le 10$。
• 对于 $50\%$ 的数据，$n,m\le 1000$。
• 对于另外 $30\%$ 的数据，保证所给出的图为一仙人掌（任意一条边至多只出现在一条环上）。
• 对于 $100\%$ 的数据，$1\le n,m\le 50000，1\le T\le 10$，保证所输入的图无重边、自环。