{"problem":{"name":"懂事时理解原神","description":{"content":"具体地，给定一个有 $n$ 个点和 $m$ 条边的无向无权图。则 dfs 求最短路的算法伪代码具体如下： ``` vis[], dis[] dfs(u): \tvis[u] = 1 \t记所有满足 u,v 之间有边且 !vis[v] 的点 v 构成的序列为 S \t以随机的顺序遍历 S:  \t\tdis[v] = dis[u] + 1 \t\tdfs(v) solve(): \tfor i in [1, n]","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8881"},"statements":[{"statement_type":"Markdown","content":"具体地，给定一个有 $n$ 个点和 $m$ 条边的无向无权图。则 dfs 求最短路的算法伪代码具体如下：\n\n```\nvis[], dis[]\ndfs(u):\n\tvis[u] = 1\n\t记所有满足 u,v 之间有边且 !vis[v] 的点 v 构成的序列为 S\n\t以随机的顺序遍历 S: \n\t\tdis[v] = dis[u] + 1\n\t\tdfs(v)\nsolve():\n\tfor i in [1, n]: \n    \tdis[i] = -1;\n        vis[i] = 0\n\tdis[1] = 0\n\tdfs(1)\n```\n\n其中，```以随机的顺序遍历 S``` 可以被理解为随机打乱 $S$，得到每一种结果的概率均为 $\\frac{1}{|S|!}$，并按照打乱后的顺序遍历。\n\n现在，胡桃想要知道，如果她调用函数 ```solve()```，得到的最短路数组 ```dis[]``` 完全正确的概率有多大。```dis[]``` 被认为完全正确，当且仅当 $\\forall i\\in[1,n]$，```dis[i]``` 的值均等于从 $1$ 到 $i$ 的最短路长度（特别地，若 $1$ 无法走到 $i$，则认为 $1$ 到 $i$ 的最短路长度为 $-1$）。\n\n## Input\n\n**本题多组询问。** 第一行输入一个数 $T$，表示询问组数。\n\n对于每组询问：\n\n第一行，两个整数 $n,m$。\n\n第二行至第 $m+1$ 行，每行两个整数 $u,v$，表示 $u,v$ 之间有一条边。\n\n## Output\n\n对于每组询问，输出一个实数，为 ```dis[]``` 数组完全正确的概率。**你需要输出答案保留三位小数（四舍五入）后的结果。**\n\n[samples]\n\n## Background\n\n胡桃喜欢用 dfs 求最短路，尽管这有可能会得到错误的答案。\n\n![](https://img2.huashi6.com/images/resource/2021/03/01/8812956h7p1.jpg?imageMogr2/quality/100/interlace/1/thumbnail/700x)\n\n画师 pid：6657532\n\n## Note\n\n- 对于 $20\\%$ 的数据，$n,m\\le 10$。\n- 对于 $50\\%$ 的数据，$n,m\\le 1000$。\n- 对于另外 $30\\%$ 的数据，保证所给出的图为一仙人掌（任意一条边至多只出现在一条环上）。\n- 对于 $100\\%$ 的数据，$1\\le n,m\\le 50000，1\\le T\\le 10$，保证所输入的图无重边、自环。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8881","tags":["图论","O2优化"],"sample_group":[["1\n5 4\n1 3\n1 2\n3 4\n2 5","1.000"],["1\n4 4\n1 2\n2 3\n3 1\n4 3","0.000"]],"created_at":"2026-03-03 11:09:25"}}