题目描述

There is a cave consisting of $N$ rooms and $M$ one-directional passages. The rooms are numbered $1$ through $N$.

Takahashi is now in Room $1$, and Room $N$ has the exit. The $i$-th passage connects Room $s_i$ and Room $t_i$ ($s_i$ < $t_i$) and can only be traversed in the direction from Room $s_i$ to Room $t_i$. It is known that, for each room except Room $N$, there is at least one passage going from that room.

Takahashi will escape from the cave. Each time he reaches a room (assume that he has reached Room $1$ at the beginning), he will choose a passage uniformly at random from the ones going from that room and take that passage.

Aoki, a friend of Takahashi's, can block one of the passages (or do nothing) before Takahashi leaves Room $1$. However, it is not allowed to block a passage so that Takahashi is potentially unable to reach Room $N$.

Let $E$ be the expected number of passages Takahashi takes before he reaches Room $N$. Find the value of $E$ when Aoki makes a choice that minimizes $E$.

有一个洞穴，由 $N$ 个房间和 $M$ 条单向通道组成。房间编号为 $1$ 至 $N$ 。

高桥现在在 $1$ 房间 $N$ 房间有出口 $i$ 这条通道连接着 $s_i$ 号房间和 $t_i$ 号房间（ $s_i$ < $t_i$ ），只能沿着 $s_i$ 号房间到 $t_i$ 号房间的方向穿越。众所周知，除了 $N$ 室之外，每个房间都至少有一条通道从该房间出去。

高桥将从洞穴中逃脱。每当他到达一个房间时（假设他一开始就到达了 $1$ 号房间），他都会从从该房间出去的通道中均匀随机地选择一条通道并走该通道。

高桥的朋友青木可以在高桥离开 $1$ 房间之前堵住其中一条通道（或者什么都不做）。但是，不允许堵塞通道，这样高桥就有可能无法到达 $N$ 房间。

设 $E$ 是高桥到达 $N$ 房间之前的预期通道数。求当青木做出最小化 $E$ 的选择时 $E$ 的值。

输入格式

输入内容按以下格式标准输入：

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

输出格式

当青木做出最小化 $E$ 的选择时，打印 $E$ 的值。当与法官输出结果的绝对误差或相对误差不超过 $10^{-6}$ 时，您的输出结果将被判定为正确。

样例 #1

样例输入 #1

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

样例输出 #1

1.5000000000

样例 #2

样例输入 #2

3 2
1 2
2 3

样例输出 #2

2.0000000000

样例 #3

样例输入 #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

说明

数据规模与约定

• $2 \leq N \leq 600$
• $N-1 \leq M \leq \frac{N(N-1)}{2}$
• $s_i \lt t_i$
• 如果 $i != j$ 、 $(s_i, t_i) \neq (s_j, t_j)$ 。（添加时间：21:23 JST）
• 对于每一个 $v = 1, 2, ..., N-1$ ，都存在 $i$ 这样的 $v = s_i$ 。

样例 $1$ 解释

如果青木封锁了从 $1$ 房间到 $2$ 房间的通道，高桥将沿着1→3→4的路径前进，概率为 $\frac{1}{2}$ ，1→4的概率为 $\frac{1}{2}$ 。这里的 $E = 1.5$ 是 $E$ 的最小可能值。

样例 $2$ 解释

封锁任何一条通道都会导致高桥无法到达 $N$ 房间，所以青木无法封锁通道。