Fork in the Road
题号：NC234833
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

有 n 个房间和 m 条单向通道。房间的编号从 1 到 n。
Takahashi 一开始在房间 1，打算走到房间 n。第 i 个通道连接房间 s_i 和 房间 t_i ()，并且只能从房间 s_i 走到房间 t_i。对于每一个房间，保证能走到房间 n。
Takahashi 每次到达一个房间，他随机选一个通道（每个通道被选中概率相同），走向下一个房间。
Takahashi 的朋友 Aoki，可以在 Takahashi 离开房间 1 之前破坏一条通道，或者什么都不做。如果破坏的这条通道导致不能到达房间 n，那么不允许破坏这条通道。
假设 E 是 Takahashi 到达房间 n 通过通道数的期望值。请计算在 Aoki 做出选择后最小的 E。

输入描述:

第一行输入 n 和 m，n 为房间数，m 为通道数。
接下来 m 行，每行两个整数s_i、t_i ，表示房间s_i能走到房间 t_i。

数据范围：



如果 那么 
保证对于每一个，存在 i 使得

输出描述:

输出最小的E。你的答案与正确答案的误差应该最多。
示例1

输入

复制 
4 6
1 4
2 3
1 3
1 2
3 4
2 4

输出

复制 
1.5000000000

说明

如果 Aoki 破环了 房间 1 和 房间 2 的通道，Takahashi 有 \frac{1}{2} 的概率走 1 \rightarrow 3 \rightarrow 4，\frac{1}{2} 的概率走 1 \rightarrow 4。因此最小的 E 是 1.5。
示例2

输入

复制 
3 2
1 2
2 3

输出

复制 
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.0133333333