Jellyfish and EVA
Contest: Codeforces Round 901 (Div. 1)
Difficulty rating: 2300
Tags: dp, graphs, greedy, math, probabilities

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<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.

Input format:
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 < 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$$$.

Output format:
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}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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$$$.

Example input:
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

Example output:
0.500000000000
0.625000000000
0.491666666667

Editorial:
Let's solve this problem by dynamic programming, Let $$$f_u$$$ represents the max probability of reaching city $$$n$$$ starting from city $$$u$$$.
The problem is how to transition. for city $$$u$$$, we assume that there are $$$d$$$ roads from city $$$u$$$, the $$$i$$$-th road from city $$$u$$$ is to city $$$v_i$$$.
Let's sort $$$v$$$ by using $$$f_v$$$ as the keyword, with $$$v$$$ with the larger $$$f_v$$$ coming first.
Let's define an array $$$a$$$ of $$$d$$$ elements equals to $$$[f_{v_1}, f_{v_2}, \dots, f_{v_d}]$$$, according to the definition, $$$a$$$ is non-increasing.
That is, next we want to find an optimal solution such that the probability of going to city $$$v_i$$$ is $$$p_i$$$, maximizing the value of $$$\sum_{i=1}^d{a_i \times p_i}$$$.
Tips: the sum of $$$p_i$$$ may not be $$$1$$$, because it is possible to stay at city $$$u$$$ when $$$d$$$ is even.
For two choices of $$$p$$$, $$$p_1$$$ and $$$p_2$$$, Sometimes we can't which is better, for example:
$$$p_1 = [0.6, 0.2, 0.2], p_2 = [0.5, 0.5, 0]$$$
when $$$a=[1.0, 0.2, 0.2]$$$, $$$p_1$$$ is better than $$$p_2$$$. But when $$$a = [1.0, 0.8, 0]$$$, $$$p_2$$$ is better than $$$p_1$$$.
Tips: In fact, when $$$d=3$$$, $$$p$$$ has only one choice $$$[\frac 1 3, \frac 1 3, \frac 1 3]$$$, the above is just a hypothetical to illustrate the problem.
So when can we say, $$$p_1$$$ is always better than $$$p_2$$$? In fact, when they satisfy the following condition, $$$p_1$$$ is always not worse than $$$p_2$$$:
$$$\forall x \leq d, \sum_{i=1}^x{p_1}_i \geq \sum_{i=1}^x{p_2}_i$$$
So for all $$$d$$$, is there an array $$$p$$$ not worse than any other arrays?
For $$$d = 1$$$, $$$p = [1.0]$$$ satisfies the condition.
For $$$d = 2$$$, $$$p = [0.5, 0]$$$ satisfies the condition.
What about $$$d>2$$$ ? After they choose the roads for the first time, The size of the problem will become $$$d - 2$$$.
For example, when $$$d = 4$$$, Let's assume Jellyfish choose $$$v_1$$$ for the first time, then there will be $$$4$$$ situations:
1. When Asuka chooses $$$v_1$$$ they will go to $$$v_1$$$.
2. When Auska chooses $$$v_2$$$, the problem changes into the subproblem with $$$[v_3, v_4]$$$.
3. When Auska chooses $$$v_3$$$, the problem changes into the subproblem with $$$[v_2, v_4]$$$.
4. When Auska chooses $$$v_4$$$, the problem changes into the subproblem with $$$[v_2, v_3]$$$.
By calculating, $$$p = [0.25, 0.25, 0.125, 0]$$$.
Let's define $$$g_k$$$ as the array $$$p$$$ when $$$d=k$$$, $$$g'_k$$$ as the the probabilities of going to cities except the city Jellyfish11037 choose for the first time. By recursion, we can get $$$g'_k$$$ from $$$g_{k-2}$$$. After that, we insert $$$\frac 1 k$$$ into $$$g'_k$$$, keeping it non-increasing, we will get $$$g_k$$$.
By calculating, we will find $$$\frac 1 k$$$ is always the first element in $$$g_k$$$. So when $$$k > 2$$$, we have the following transition:
$$$g_{k, 1} = \frac 1 k$$$
$$$\forall 1 < i \leq k, g_{k, i} = g_{k-2, i - 2} \times \frac {i - 1} k + g_{k-2, i - 1} \times \frac {k - i} k$$$
In the above we think $$$g_{k, x}=0$$$ for all $$$x = 0$$$ or $$$x > k$$$.
Time complexity: $$$O(n^2 + m \log n)$$$ per test case. (Moreover, we can get $$$g$$$ before all the test cases, So there's actually no need for guarantee the sum of $$$n$$$)