洞穴脱出

题目描述

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

高桥君现在在房间 $1$，房间 $N$ 与出口相连。第 $i$ 条通道连接房间 $s_i$ 和房间 $t_i$（$s_i \lt t_i$），只能从房间 $s_i$ 向房间 $t_i$ 方向通行。已知除房间 $N$ 外的每个房间，至少存在一条从该房间出发的通道。

高桥君试图从这个洞穴逃脱。每次到达一个房间时（脱出开始时视为已到达房间 $1$），高桥君会从该房间出发的通道中等概率地随机选择一条前进。

高桥君的朋友青木君可以在高桥君从房间 $1$ 出发之前，堵住一条通道（或者什么也不做）。但是，不能堵住会导致高桥君可能无法到达房间 $N$ 的通道。

设高桥君到达房间 $N$ 之前所经过的通道数的期望值为 $E$。求青木君作出使 $E$ 最小化的选择时的 $E$ 值。

输入格式

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

$N$ $M$
$s_1$ $t_1$
$:$
$s_M$ $t_M$

输出格式

输出青木君作出使 $E$ 最小化的选择时的 $E$ 值。 当输出与标准答案的绝对误差或相对误差不超过 $10^{-6}$ 时，判定为正确。

样例

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

1.5000000000

若青木君堵住从房间 $1$ 到房间 $2$ 的通道，高桥君以 $\frac{1}{2}$ 的概率沿 1 → 3 → 4 的路径前进，以 $\frac{1}{2}$ 的概率沿 1 → 4 的路径前进。此时 $E = 1.5$，这是 $E$ 可能取到的最小值。

3 2
1 2
2 3

2.0000000000

无论堵住哪条通道都会导致无法到达房间 $N$，因此青木君不能堵住任何通道。

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

数据范围

• $2 \le N \le 600$
• $N-1 \le M \le \frac{N(N-1)}{2}$
• $s_i \lt t_i$
• 当 $i \neq j$ 时，$(s_i, t_i) \neq (s_j, t_j)$
• 对任意 $v = 1, 2, ..., N-1$，存在某个 $i$ 使得 $v = s_i$