CF679D Bear and Chase

熊国有 $n$ 个城市，编号为 $1$ 到 $n$。有 $m$ 条双向道路，第 $i$ 条道路连接两个不同的城市 $a_i$ 和 $b_i$。不存在有两条道路连接同一对城市。任意两个城市之间都可以通过一条或多条道路到达。 城市 $a$ 与城市 $b$ 之间的距离定义为从 $a$ 到 $b$ 需要经过的最少道路数。 Limak 是一只灰熊，也是个罪犯。你的任务是抓住他，或至少尽力抓住他。你只有两天（今天和明天），之后 Limak 就会永远躲藏起来。 你的主要工具是 BCD（Bear Criminal Detector，熊罪犯探测仪）。你可以在任意城市使用 BCD，BCD 会告诉你你与 Limak 当前所在城市之间的距离。不幸的是，BCD 每天只能使用一次。 你对 Limak 的当前位置知之甚少。你只能假设他目前均匀随机地位于 $n$ 个城市中的某一个（每个城市的概率均相等）。你决定采取如下计划： 1. 选择一个城市并使用 BCD。 - 使用 BCD 后你可以尝试立即抓捕 Limak（但这不一定是好主意）。此时你可选择任一城市进行检查。若 Limak 正在该城市你就获胜，否则 Limak 会变得更加谨慎，你将再也无法抓到他（游戏失败）。 2. 等待 $24$ 小时后，再次使用 BCD。在这期间，Limak 会改变位置：具体来说，他会从他原本所在的城市均匀随机地选择一条道路，沿这条路前往相邻的另一个城市。 3. 第二天你可以再次选择一个城市并使用 BCD。 4. 最后你将尝试抓捕 Limak。你选择一个城市进行检查。若 Limak 当前在该城市你就获胜，否则游戏失败。 每次你选择一个城市时，可以任意选择 $n$ 个城市中的任何一个。可以认为你能以极快的速度到达任何地方。 如果你始终采取最优策略，最终抓到 Limak 的概率是多少？

输入的第一行包含两个整数 $n$ 和 $m$（$2\leq n\leq 400$，$1\leq m\leq n(n-1)/2$），分别表示城市数和道路数。 接下来 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1\leq a_i,b_i\leq n$，$a_i\neq b_i$），表示第 $i$ 条道路连接的两个城市。 不存在有两条道路连接同一对城市。任意两个城市之间都可到达。

输出一个实数，表示最优策略下抓到 Limak 的概率。你的答案只要绝对误差不超过 $10^{-6}$ 即可。 即，设你的答案为 $a$，标准答案为 $b$，当 $|a-b|\leq 10^{-6}$ 时你的输出将被视为正确。

在第一个样例中，有三个城市，且每一对都有一条道路相连。分析最优方案如下： 1. 在城市 $1$ 使用 BCD： - 以概率 $\frac{1}{3}$ Limak 就在该城市，BCD 会显示距离为 $0$。此时你应立即尝试抓捕他，必定成功。 - 以概率 $\frac{2}{3}$，距离为 $1$，因为 Limak 在城市 $2$ 或 $3$。此时应等待至第二天。 2. 你选择等待，这期间 Limak 会移动到其它城市。 - Limak 初始在城市 $2$ 并移到城市 $3$ 的概率是 $\frac{1}{6}$。 - 从 $2$ 到 $1$ 的概率也是 $\frac{1}{6}$。 - 从 $3$ 到 $2$ 的概率是 $\frac{1}{6}$。 - 从 $3$ 到 $1$ 的概率是 $\frac{1}{6}$。 3. 第二天你再次在城市 $1$ 使用 BCD（当然也可以选择其它城市，但此处选择 $1$）。 - 若此时距离为 $0$，你便能确定 Limak 就在眼前（获胜）。 - 若距离为 $1$，Limak 在城市 $2$ 或 $3$，此时你只能猜一个城市，如果猜错就失败（成功概率 $1/2$）。 唯一失败的情况是 Limak 原本在城市 $2$，然后移动到城市 $3$。失败概率是 $\frac{1}{6}$，因此最终答案是 $1-\frac{1}{6}=\frac{5}{6}$。 由 ChatGPT 5 翻译