题目描述

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

高桥现在在房间 $1$，房间 $N$ 是出口。第 $i$ 条通道连接房间 $s_i$ 和房间 $t_i$ ($s_i$ < $t_i$)，只能从房间 $s_i$ 出发顺时针穿越到房间 $t_i$。已知除了房间 $N$ 外，每个房间都至少有一条通道从该房间通向其他房间。

高桥要逃离洞穴。每次他到达一个房间（假设一开始他到达房间 $1$），他会从该房间的通道中均匀随机地选择一条通道，并走过那条通道。

高桥的朋友 Aoki 可以在高桥离开房间 $1$ 之前封锁一条通道（或者不采取任何行动）。但是，不允许封锁一条通道以致于高桥有可能无法到达房间 $N$。

设 $E$ 为高桥到达房间 $N$ 前所经过的通道的期望数量。找到使 $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)$。(添加于 21:23 JST)
• 对于每个 $v = 1, 2, ..., N-1$，存在一个 $i$，使得 $v = s_i$。

输入

从标准输入读取输入数据格式如下：

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

输出

当 Aoki 采取使 $E$ 最小化的行动时，打印出 $E$ 的值。只要与评判输出的绝对误差或相对误差不超过 $10^{-6}$，你的输出就会被判断为正确。

示例输入 1

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

示例输出 1

1.5000000000

如果 Aoki 封锁了从房间 $1$ 到房间 $2$ 的通道，高桥将以概率 $\\frac{1}{2}$ 沿着路径 1 → 3 → 4 前进，并以概率 $\\frac{1}{2}$ 沿着路径 1 → 4 前进。在这种情况下，$E = 1.5$，并且这是 $E$ 的最小可能值。

示例输入 2

3 2
1 2
2 3

示例输出 2

2.0000000000

封锁任一条通道都会使高桥无法到达房间 $N$，所以 Aoki 不能封锁通道。

示例输入 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