Bearland 有 n 个城市,编号为 1 到 n。有m条双向道路。第 i 条路连接两个不同的城市 ai 和 bi。没有两条道路连接同一对城市。可以从任何城市前往任何其他城市(使用一条或多条道路)。
城市 a 和 b 之间的距离定义为 a 和 b 之间行驶所用道路的最少数量。
Limak 是一只灰熊。他是一个罪犯,你的任务就是抓住他,或者至少尝试抓住他。你只有两天的时间(今天和明天),之后利马克将永远隐藏起来。
你的主要武器是BCD(熊犯罪探测器)。当你在某个城市时,你可以使用BCD,它会告诉你你和Limak当前所在城市之间的距离。不幸的是,BCD 每天只能使用一次。
你对利马克当前的位置不太了解。您假设他位于 n 个城市之一,均匀随机选择(每个城市的概率为 $${\frac {1}{n}}$$)。您决定执行以下计划:
1. 选择一个城市并在那里使用 BCD。 使用BCD后你可以尝试抓住Limak(但这也许不是一个好主意)。在这种情况下,您选择一个城市并进行检查。如果利马克在,你就赢了。否则,利马克会变得更加小心,你永远不会抓住他(你会松手)。
2. 等待 24 小时才能再次使用 BCD。你知道利马克在那段时间会改变他的位置。具体来说,他会从他最初的城市统一随机选择一条道路,然后他会使用所选择的道路,前往另一个城市。
3.明天,您将再次选择一个城市并在那里使用BCD。
4. 最后,您将尝试抓住 Limak。您将选择一个城市并进行检查。如果利马克在,你就会赢,否则就输。
每次选择一个城市时,您可以选择n个城市中的任意一个。假设您快速到达某个地方不是问题。
如果您表现最佳,找到 Limak 的概率是多少?
输入
输入的第一行包含两个整数 n 和 m (2 ≤ n ≤ 400, $$n-1 \leq m \leq \frac{n(n-1)}{2}$$) - 分别是城市数量和道路数量。
然后,接下来是 m 行。其中第 i 个包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ n, ai ≠ bi) - 由第 i 条道路连接的城市。
没有两条道路连接同一对城市。从任何一个城市到任何其他城市都是可能的。
输出
打印一个实数——如果您表现最佳,找到 Limak 的概率。如果绝对误差不超过 10 - 6,您的答案将被视为正确。
即:假设你的答案是a,陪审团的答案是b。如果|a - b|,检查程序将认为您的答案正确。 ≤ 10 - 6。
示例
输入 #1
3 3 1 2 1 3 2 3
输出 #1
0.833333333333
输入 #2
5 4 1 2 3 1 5 1 1 4
输出 #2
1.000000000000
输入 #3
4 4 1 2 1 3 2 3 1 4
输出 #3
0.916666666667
输入#4
5 5 1 2 2 3 3 4 4 5 1 5
输出#4
0.900000000000
注意
在第一个样本测试中,有三个城市,每对城市之间有一条道路。让我们分析一种最佳场景。
1. 在城市 1 使用 BCD。有概率 $${\frac {1}{3}}$$ Limak 在这个城市,BCD 告诉你距离为 0。你现在应该尝试抓住他,你一定会赢。 概率 $$\frac{2}{3}$$ 距离为 1,因为 Limak 位于城市 2 或城市 3。在这种情况下,您应该等待第二天。
2. 您等待,Limak 会搬到其他城市。 利马克有可能 $$\frac{1}{3} \cdot \frac{1}{2}$$ 在城市 2,然后去了城市 3。 $$\frac{1}{3} \cdot \frac{1}{2}$$ 他从 2 到 1。 $$\frac{1}{3} \cdot \frac{1}{2}$$ 他从 3 到 2。 $$\frac{1}{3} \cdot \frac{1}{2}$$ 他从 3 变成了 1。
3.在城市1再次使用BCD(尽管在其他城市允许使用它)。 如果距离为 0,则您确定 Limak 位于这座城市(您获胜)。 如果距离为 1,那么 Limak 在城市 2 或城市 3。那么你应该猜测他在城市 2(猜测城市 3 也可以)。
只有当 Limak 首先在城市 2 然后他搬到城市 3 时,你才会输。输的概率为 $$\frac{1}{3} \cdot \frac{1}{2} = \frac{1}{6}$$。答案是$$1 - \frac { 1 } { 6 } = \frac { 5 } { 6 }$$。