怪物再次入侵城镇!明日香邀请她的好朋友水母一起驾驶 EVA。
城镇中有 $$$n$$$ 个城市。所有怪物都在城市$$$n$$$。水母和明日香目前在城市$$$1$$$,需要移动到城市$$$n$$$来击败怪物。
有 $$$m$$$ 条道路。第 $$$i$$$ 条道路允许人们从城市 $$$a_i$$$ 前往城市 $$$b_i$$$。所有的道路都是有方向的。也就是说,人们无法使用第 $$$i$$$ 条道路从城市 $$$b_i$$$ 前往 $$$a_i$$$。有趣的是,所有道路都满足$$$a_i<b_i$$$。
驾驶EVA需要两个人一起工作。不过,明日香和水母之前并没有一起进行过任何训练。
假设 EVA 目前位于城市 $$$u$$$。水母和明日香都会选择一条从 $$$u$$$ 城市开始的未受破坏的道路。假设 Jellyfish 和 Asuka 选择分别以城市 $$$v_1$$$ 和 $$$v_2$$$ 为终点的道路。如果$$$v_1 = v_2$$$,则EVA成功移动到城市$$$v_1$$$。否则,EVA 会留在城市 $$$u$$$ 并且他们选择的两条道路都将被摧毁。
EVA 当前可能位于城市 $$$u$$$ ($$$u \neq n$$$) 并且没有从城市 $$$u$$$ 开始的未毁坏道路。那样的话,任务就会失败。否则,如果最终到达城市$$$n$$$,则视为任务成功。
每次选择道路时,水母都知道明日香会随机选择一条道路。现在,水母想知道,如果她选择最佳道路,任务成功的最大概率是多少。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 2000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数,$$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 5000$$$, $$$0 \leq m \leq \min(\frac{n(n-1)}{2}, 2 \cdot 10^5)$$$) — 城市数量和道路数量。
在每个测试用例的以下 $$$m$$$ 行中,每行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \leq a < b \leq n$$$) - 表示从城市 $$$a$$$ 到城市 $$$b$$$ 的道路。
保证对于每个测试用例,每条路最多出现一次。
保证所有测试用例的 $$$n$$$ 总和不会超过 $$$5000$$$,并且所有测试用例的 $$$m$$$ 总和不会超过 $$$2 \cdot 10^5$$$。
输出
输出如果 Jellyfish 选择最佳道路,任务成功的最大概率。
如果绝对或相对误差不超过 $$$10^{-9}$$$,您的答案将被接受。正式来说,让您的答案为$$$a$$$,陪审团的答案为$$$b$$$。如果 $$$\frac{|a-b|}{\max(1,|b|)} \leq 10^{-9}$$$,则认为您的答案是正确的。
示例
输入 #1
3 3 2 1 2 1 3 7 8 1 2 1 3 1 4 1 5 2 6 3 6 4 6 6 7 10 20 1 2 1 3 1 4 1 5 1 6 2 6 2 7 2 8 2 9 3 4 3 7 3 8 3 10 4 6 4 8 4 10 6 10 7 8 7 9 7 10
输出 #1
0.500000000000 0.625000000000 0.491666666667
注意
在第一个测试用例中,Jellyfish 将选择 $$$v_1=3$$$,Asuka 将选择 $$$v_2=2$$$(可能性为 $$$0.5$$$)和 $$$v_2=3$$$(可能性为 $$$0.5$$$)。该任务被视为成功,可能性为 $$$0.5$$$。