AT_abc144_f [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$，因此青木君不能封锁任何通道。 由 ChatGPT 4.1 翻译