配点 : $600$ 点

問題文

$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$ の値を求めてください。

制約

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

入力

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

$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