题目描述

$N$ 個の部屋と、$M$ 本の一方向にのみ通れる通路から成る洞窟があります。部屋には $1$ から $N$ までの番号がついています。

高橋君はいま部屋 $1$ におり、部屋 $N$ が出口へと繋がっています。$i$ 番目の通路は部屋 $s_i$ と部屋 $t_i$ ( $s_i$ < $t_i$ ) を繋いでおり、部屋 $s_i$ から部屋 $t_i$ の方向にのみ通ることが出来ます。部屋 $N$ 以外の各部屋について、その部屋から出る通路が少なくとも $1$ つ存在することが分かっています。

高橋君はこの洞窟から脱出を試みます。部屋に到達するたびに (脱出開始時は部屋 $1$ に到達したとみなします)、高橋君はその部屋から出る通路のうち等確率でランダムに $1$ つを選んで進みます。

高橋君の友達の青木君は、高橋君が部屋 $1$ から移動する前に $1$ つだけ通路を塞ぐ (または何もしない) ことが出来ます。ただし、高橋君が部屋 $N$ に到達できなくなる可能性が生じるような通路の塞ぎ方は出来ません。

高橋君が部屋 $N$ に到達するまでに通る通路の数の期待値を $E$ とします。青木君が $E$ を最小化するような選択をしたときの $E$ の値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

青木君が $E$ を最小化するような選択をしたときの $E$ の値を出力せよ。 出力は、ジャッジと出力との絶対誤差または相対誤差が $10^{-6}$ 以下のとき正解と判定される。

题目大意

有 $N$ 个房间（从 $1$ 到 $N$ 编号），$M$ 条单向通道，每条通道从 $s_i$ 到 $t_i$ $(si<ti)$。

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

高桥现在在 $1$ 号房间，要到达 $N$ 号房间。每次他会从当前房间的通道中等概率随机选择一个通道行走。

高桥的朋友青木，可以在高桥离开 $1$ 号房间前，堵住其中一条通道（或什么都不做）。

但是，不允许堵住一条通道，使高桥有可能无法到达 $N$ 号房间。

设 $E$ 为高桥在到达 $N$ 号房间要走的通道数的期望，青木要堵住某条通道（或什么都不做）使 $E$ 最小。

输出最小的 $E$ ，误差不超过 $10^{-6}$ 即视为正确 。

数据范围：$2 \leqslant N \leqslant 600\ ,N-1 \leqslant M \leqslant {N(N-1)\over 2}$ ，无重边。

保证初始每个点都存在至少一条路径到达 $N$。

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

1.5000000000

3 2
1 2
2 3

2.0000000000

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\ <\ =\ 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)$ (21:23 追記)
• 任意の $v\ =\ 1,\ 2,\ ...,\ N-1$ に対し、ある $i$ が存在して $v\ =\ s_i$

Sample Explanation 1

青木君が部屋 $1$ から部屋 $2$ への通路を塞ぐと、高橋君は $\frac{1}{2}$ の確率で 1 → 3 → 4 という経路を辿り、 $\frac{1}{2}$ の確率で 1 → 4 という経路を辿ります。このとき $E\ =\ 1.5$ であり、これが $E$ がとりうる最小の値です。

Sample Explanation 2

どの通路を塞いでも部屋 $N$ に到達出来なくなるため、青木君は通路を塞ぐことは出来ません。