懂事时理解原神
题目背景
胡桃喜欢用 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
1
5 4
1 3
1 2
3 4
2 5输出样例 #1
1.000输入样例 #2
1
4 4
1 2
2 3
3 1
4 3输出样例 #2
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$，保证所输入的图无重边、自环。