题目描述

有 $N$ 个房间和 $M$ 条只能单向通行的通道组成的洞窟。每个房间编号为 $1$ 到 $N$。

高桥君现在在房间 $1$，房间 $N$ 是出口。第 $i$ 条通道连接房间 $s_i$ 和房间 $t_i$（$s_i < t_i$），只能从房间 $s_i$ 走向房间 $t_i$。已知除了房间 $N$ 以外，每个房间至少有一条出发的通道。

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

高桥君的朋友青木君可以在高桥君从房间 $1$ 出发前，选择封锁一条通道（也可以什么都不做）。但不能封锁导致高桥君无法到达房间 $N$ 的通道。

设高桥君到达房间 $N$ 前经过的通道数的期望为 $E$。请你求出青木君在使 $E$ 最小化的情况下，$E$ 的值。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$
$s_1$ $t_1$
$s_2$ $t_2$
$\vdots$
$s_M$ $t_M$

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

1.5000000000

输入输出样例 #2

输入 #2

3 2
1 2
2 3

输出 #2

2.0000000000

输入输出样例 #3

输入 #3

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

3.0133333333

说明/提示

限制条件

• $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)$（2021-11-23 补充）
• 对于任意 $v = 1, 2, \ldots, N-1$，存在某个 $i$ 使得 $v = s_i$

样例解释 1

如果青木君封锁了从房间 $1$ 到房间 $2$ 的通道，高桥君有 $\frac{1}{2}$ 的概率走 1 → 3 → 4，有 $\frac{1}{2}$ 的概率走 1 → 4。此时 $E = 1.5$，这是 $E$ 能取得的最小值。

样例解释 2

无论封锁哪条通道，高桥君都无法到达房间 $N$，因此青木君不能封锁任何通道。