懂事时理解原神

具体地，给定一个有 $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$）。 ## Input **本题多组询问。** 第一行输入一个数 $T$，表示询问组数。 对于每组询问： 第一行，两个整数 $n,m$。 第二行至第 $m+1$ 行，每行两个整数 $u,v$，表示 $u,v$ 之间有一条边。 ## Output 对于每组询问，输出一个实数，为 ```dis[]``` 数组完全正确的概率。**你需要输出答案保留三位小数（四舍五入）后的结果。** [samples] ## Background 胡桃喜欢用 dfs 求最短路，尽管这有可能会得到错误的答案。  画师 pid：6657532 ## Note - 对于 $20\%$ 的数据，$n,m\le 10$。 - 对于 $50\%$ 的数据，$n,m\le 1000$。 - 对于另外 $30\%$ 的数据，保证所给出的图为一仙人掌（任意一条边至多只出现在一条环上）。 - 对于 $100\%$ 的数据，$1\le n,m\le 50000，1\le T\le 10$，保证所输入的图无重边、自环。