A7566. [ABC144F] Fork in the Road

有 $N$ 个房间和 $M$ 条只能单向通行的通道组成的洞窟。每个房间编号为 $1$ 到 $N$。

高桥君现在在房间 $1$，房间 $N$ 是出口。第 $i$ 条通道连接房间 $s_i$ 和房间 $t_i$（$s_i < t_i$），只能从房间 $s_i$ 走向房间 $t_i$。已知除了房间 $N$ 以外，每个房间至少有一条出发的通道。

高桥君尝试从洞窟中逃脱。每当他到达一个房间时（开始时视为到达房间 $1$），他会等概率随机选择一条从该房间出发的通道前进。

高桥君的朋友青木君可以在高桥君从房间 $1$ 出发前，选择封锁一条通道（也可以什么都不做）。但不能封锁导致高桥君无法到达房间 $N$ 的通道。

设高桥君到达房间 $N$ 前经过的通道数的期望为 $E$。请你求出青木君在使 $E$ 最小化的情况下，$E$ 的值。

输入通过标准输入给出，格式如下：

> $N$ $M$
> $s_1$ $t_1$
> $s_2$ $t_2$
> $\vdots$
> $s_M$ $t_M$

输出青木君在使 $E$ 最小化的情况下，$E$ 的值。
当你的输出与标准答案的绝对误差或相对误差不超过 $10^{-6}$ 时，将被判定为正确。

## 限制条件

- $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)$（2021-11-23 补充）
- 对于任意 $v = 1, 2, \ldots, N-1$，存在某个 $i$ 使得 $v = s_i$

## 样例解释 1

如果青木君封锁了从房间 $1$ 到房间 $2$ 的通道，高桥君有 $\frac{1}{2}$ 的概率走 1 → 3 → 4，有 $\frac{1}{2}$ 的概率走 1 → 4。此时 $E = 1.5$，这是 $E$ 能取得的最小值。

## 样例解释 2

无论封锁哪条通道，高桥君都无法到达房间 $N$，因此青木君不能封锁任何通道。