怪物再次入侵了城镇！Asuka 邀请她的好朋友 Jellyfish 和她一起驾驶 EVA。

城镇中有 $n$ 个城市。所有的怪物都在城市 $n$。Jellyfish 和 Asuka 目前在城市 1，需要前往城市 $n$ 来击败怪物。

城镇中有 $m$ 条道路。第 $i$ 条道路允许从城市 $a_i$ 前往城市 $b_i$。所有的道路都是有向的。也就是说，不能通过第 $i$ 条道路从城市 $b_i$ 前往 $a_i$。有趣的是，所有道路都满足 $a_i < b_i$。

驾驶 EVA 需要两个人共同协作。然而，Asuka 和 Jellyfish 之前从未一起训练过。

假设 EVA 目前在城市 $u$。Jellyfish 和 Asuka 将各自选择一条从城市 $u$ 出发的未被摧毁的道路。假设 Jellyfish 和 Asuka 选择的道路分别通向城市 $v_1$ 和 $v_2$。如果 $v_1 = v_2$，EVA 成功移动到城市 $v_1$。否则，EVA 将停留在城市 $u$，且她们选择的两条道路都会被摧毁。

如果 EVA 目前在城市 $u$ ($u \neq n$) 且没有从城市 $u$ 出发的未被摧毁的道路，那么任务就会失败。否则，如果她们最终到达了城市 $n$，则任务被视为成功。

每次她们选择道路时，Jellyfish 都知道 Asuka 会随机选择一条道路。现在，Jellyfish 想知道，如果她选择道路的策略是最优的，那么任务成功的最大概率是多少。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 2000$)。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 5000, 0 \le m \le \min(\frac{n(n-1)}{2}, 2 \cdot 10^5)$) —— 城市数量和道路数量。

在接下来的 $m$ 行中，每行包含两个整数 $a$ 和 $b$ ($1 \le a < b \le n$) —— 表示一条从城市 $a$ 到城市 $b$ 的道路。

保证对于每个测试用例，每条道路最多出现一次。

保证所有测试用例中 $n$ 的总和不超过 5000，且所有测试用例中 $m$ 的总和不超过 $2 \cdot 10^5$。

输出格式

输出如果 Jellyfish 采取最优策略，任务成功的最大概率。

如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-9}$，则你的答案将被接受。形式上，设你的答案为 $a$，评测系统的答案为 $b$，如果 $\frac{|a-b|}{\max(1, |b|)} \le 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 会以 0.5 的概率选择 $v_2 = 2$，以 0.5 的概率选择 $v_2 = 3$。任务成功的概率为 0.5。