CF1874C Jellyfish and EVA

怪兽们又一次入侵了小镇！明日香邀请了她的好朋友水母一起驾驶 EVA。 小镇里有 $n$ 个城市。所有怪兽都在第 $n$ 个城市。水母和明日香现在在第 $1$ 个城市，需要前往第 $n$ 个城市去打败怪兽。 有 $m$ 条道路。第 $i$ 条道路可以让人从城市 $a_i$ 前往城市 $b_i$。所有道路都是有向的，也就是说不能通过第 $i$ 条道路从 $b_i$ 前往 $a_i$。有趣的是，所有道路都满足 $a_i < b_i$。 驾驶 EVA 需要两个人协作。然而，明日香和水母之前从未一起训练过。 假设 EVA 当前在城市 $u$。水母和明日香都会选择一条从城市 $u$ 出发且尚未被摧毁的道路。假设水母和明日香分别选择的道路通向城市 $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$。

输出如果水母每次都最优选择道路，任务成功的最大概率。 如果你的答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。形式化地说，设你的答案为 $a$，标准答案为 $b$，当 $\frac{|a-b|}{\max(1,|b|)} \leq 10^{-9}$ 时，视为正确。

在第一个测试用例中，水母会选择 $v_1=3$，明日香会以 $0.5$ 的概率选择 $v_2=2$，以 $0.5$ 的概率选择 $v_2=3$。任务成功的概率为 $0.5$。 由 ChatGPT 4.1 翻译