题目描述

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

Takahashi现在在房间1，而房间$N$是出口。

第$i$条通道连接房间$s_i$和房间$t_i(s_i<t_i)$，只能从房间$s_i$沿着方向前往房间$t_i$。

已知，除了房间$N$以外的每个房间，都至少有一条通道从该房间出发。

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

akahashi的朋友AoKi可以在akahashi离开房间1之前阳止一条通道(或什么都不做)。

不允许阳止一条通道，从而使Takahashi有可能到达不了房间$N$。

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

输入

第一行两个整数$N,M$

接下来一共$M$对整数，表示$s_i,t_i$

输出

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

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

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

1.5000000000

样例解释

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

3 2
1 2
2 3

2.0000000000

样例解释

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

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

样例解释

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

提示

• $2\ <\ =\ N\ <\ =\ 600$
• $N-1\ <\ =\ M\ <\ =\ \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$