P8881 懂事时理解原神
题目背景
胡桃喜欢用 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$）。
输入格式
无
输出格式
无
说明/提示
- 对于 $20\%$ 的数据，$n,m\le 10$。
- 对于 $50\%$ 的数据，$n,m\le 1000$。
- 对于另外 $30\%$ 的数据，保证所给出的图为一仙人掌（任意一条边至多只出现在一条环上）。
- 对于 $100\%$ 的数据，$1\le n,m\le 50000，1\le T\le 10$，保证所输入的图无重边、自环。