CF1874C.Jellyfish and EVA

Monsters have invaded the town again! Asuka invites her good friend, Jellyfish, to drive EVA with her.

There are $n$ cities in the town. All the monsters are in city $n$. Jellyfish and Asuka are currently in city $1$ and need to move to city $n$ to defeat the monsters.

There are $m$ roads. The $i$-th road allows one to travel from city $a_i$ to city $b_i$. All the roads are directed. That is, one cannot travel from city $b_i$ to $a_i$ using the $i$-th road. Interestingly, all roads satisfy $a_i \lt b_i$.

Driving EVA requires two people to work together. However, Asuka and Jellyfish have not done any training together before.

Suppose that EVA is currently in city $u$. Jellyfish and Asuka will both choose an undestroyed road that starts at city $u$. Suppose Jellyfish and Asuka choose roads that end at cities $v_1$ and $v_2$ respectively. If $v_1 = v_2$, EVA moves to city $v_1$ successfully. Otherwise, EVA stays in city $u$ and both roads that they have chosen will be destroyed.

It is possible that EVA is currently in city $u$ ($u \neq n$) and there are no undestroyed roads that start at city $u$. In that case, the mission will be a failure. Otherwise, if they reach city $n$ in the end, the mission is considered a success.

Every time they choose the roads, Jellyfish knows that Asuka will choose a road randomly. Now, Jellyfish wants to know, if she chooses the roads optimally, what is the maximum probability of the mission being successful.

怪物再次入侵了小镇！明日香邀请她的好朋友水母一起驾驶EVA。

小镇共有 $n$ 座城市，所有怪物都聚集在第 $n$ 座城市。明日香和水母当前位于第 $1$ 座城市，需要前往第 $n$ 座城市击败怪物。

小镇中有 $m$ 条道路。第 $i$ 条道路允许从城市 $a_i$ 单向通行至城市 $b_i$。所有道路均为有向边，即无法通过第 $i$ 条道路从城市 $b_i$ 返回城市 $a_i$。有趣的是，所有道路均满足 $a_i \lt 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$，则任务视为成功。

每次选择道路时，水母知道明日香将随机选择一条可选道路。现在，水母希望知道：若她每次都以最优策略选择道路，任务成功的最大概率是多少？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 2000$). The description of the test cases follows.

The first line of each test case contains two integers, $n$ and $m$ ($2 \leq n \leq 5000$, $0 \leq m \leq \min(\frac{n(n-1)}{2}, 2 \cdot 10^5)$) — the number of the cities and the number of the roads.

In the following $m$ lines of each test case, each line contains two integers $a$ and $b$ ($1 \leq a \lt b \leq n$) — representing a road from city $a$ to city $b$.

It is guaranteed that for each test case, each road appears at most once.

It is guaranteed that the sum of $n$ over all test cases will not exceed $5000$ and that the sum of $m$ over all test cases will not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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 \lt b \leq n$），表示一条从城市 $a$ 到城市 $b$ 的道路。

保证在每个测试用例中，每条道路至多出现一次。

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

Output the maximum probability of the mission being successful if Jellyfish chooses the roads optimally.

Your answer will be accepted if the absolute or relative error does not exceed $10^{-9}$. Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is considered correct if $\frac{|a-b|}{\max(1,|b|)} \leq 10^{-9}$.

如果水母（Jellyfish）最优地选择道路，输出任务成功的最大概率。

若你的答案的绝对误差或相对误差不超过 $10^{-9}$，则该答案将被接受。形式化地说，设你的答案为 $a$，评测组的答案为 $b$，当且仅当 $\frac{|a-b|}{\max(1,|b|)} \leq 10^{-9}$ 时，你的答案被视为正确。

In the first test case, Jellyfish will choose $v_1=3$, and Asuka will choose $v_2=2$ with a possibility of $0.5$ and $v_2=3$ with a possibility of $0.5$. The mission is considered a success with a possibility of $0.5$.

在第一个测试用例中，Jellyfish 将选择 $v_1=3$，而 Asuka 将以 $0.5$ 的概率选择 $v_2=2$，以 $0.5$ 的概率选择 $v_2=3$。任务成功的概率为 $0.5$。