F - 分岔路口

得分：600分

问题陈述

有一个由$N$个房间和$M$条单向通道构成的洞穴，房间编号从$1$到$N$。

Takahashi现在在房间$1$，而房间$N$是出口。第$i$条通道连接房间$s_i$和房间$t_i$ ($s_i < t_i$)，只能从房间$s_i$沿着方向前往房间$t_i$。已知，除了房间$N$以外的每个房间，都至少有一条通道从该房间出发。

Takahashi将逃离洞穴。每次他进入一个房间（假设他最初进入了房间$1$），他将从该房间的通道中均匀随机选择一条通道并走过去。

Takahashi的朋友Aoki可以在Takahashi离开房间$1$之前阻止一条通道（或什么都不做）。不允许阻止一条通道，从而使Takahashi有可能到达不了房间$N$。

设$E$为Takahashi到达房间$N$之前所走过的通道数量的期望值。找出当Aoki做出使$E$最小化的选择时的$E$的值。

约束条件

• $2 \leq N \leq 600$
• $N-1 \leq M \leq \frac{N(N-1)}{2}$
• $s_i < t_i$
• 若$i \neq j$，则$(s_i, t_i) \neq (s_j, t_j)$。
• 对于每个$v = 1, 2, ..., N-1$，存在$i$使得$v = s_i$。

输入

从标准输入中以以下格式给出输入：

$N$ $M$

$s_1$ $t_1$

...

$s_M$ $t_M$

输出

打印当Aoki做出使$E$最小化的选择时的$E$的值。

当您的输出与参考输出的绝对误差或相对误差至多为$10^{-6}$时，您的输出将被视为正确。

4 6
1 4
2 3
1 3
1 2
3 4
2 4

1.5000000000

If Aoki blocks the passage from Room $1$ to Room $2$, Takahashi will go along the path 1 → 3 → 4 with probability $\frac{1}{2}$ and 1 → 4 with probability $\frac{1}{2}$. $E = 1.5$ here, and this is the minimum possible value of $E$.

3 2
1 2
2 3

2.0000000000

Blocking any one passage makes Takahashi unable to reach Room $N$, so Aoki cannot block a passage.

10 33
3 7
5 10
8 9
1 10
4 6
2 5
1 7
6 10
1 4
1 3
8 10
1 5
2 6
6 9
5 6
5 8
3 6
4 8
2 7
2 9
6 7
1 2
5 9
6 8
9 10
3 9
7 8
4 5
2 10
5 7
3 5
4 7
4 9

3.0133333333

样例解释

输入1：当Aoki阻止从房间$1$到房间$2$的通道时，Takahashi将以概率$\frac{1}{2}$沿路径$1 \rightarrow 3 \rightarrow 4$前进，以概率$\frac{1}{2}$沿路径$1 \rightarrow 4$前进。此时$E = 1.5$，且这是$E$的最小可能值。

输入2：阻止任何一条通道都会使Takahashi无法到达房间$N$，因此Aoki不能阻止通道。

输入3：在这个例子中，Aoki可以选择阻止从房间$1$到房间$7$的通道，这样$E$的值最小，为$3.0133333333$。