AT_abc218_f [ABC218F] Blocked Roads

给定一个有 $N$ 个顶点、$M$ 条边的有向图。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边（$1 \leq i \leq M$）是从顶点 $s_i$ 指向顶点 $t_i$ 的长度为 $1$ 的有向边。 对于每个 $i$（$1 \leq i \leq M$），请你求出当且仅第 $i$ 条边无法通过时，从顶点 $1$ 到顶点 $N$ 的最短距离。如果无法从顶点 $1$ 到达顶点 $N$，则输出 $-1$。

输入以如下格式从标准输入读入。 > $N$ $M$ > $s_1$ $t_1$ > $s_2$ $t_2$ > $\vdots$ > $s_M$ $t_M$

输出 $M$ 行。 第 $i$ 行输出当且仅第 $i$ 条边无法通过时，从顶点 $1$ 到顶点 $N$ 的最短距离。如果无法到达，则输出 $-1$。

### 限制条件 - $2 \leq N \leq 400$ - $1 \leq M \leq N(N-1)$ - $1 \leq s_i, t_i \leq N$ - $s_i \neq t_i$ - $(s_i, t_i) \neq (s_j, t_j)$（$i \neq j$） - 所有输入均为整数。 ### 样例解释 2 当且仅第 $1$ 条边无法通过时，无法从顶点 $1$ 到达顶点 $N$，因此输出 $-1$。 由 ChatGPT 4.1 翻译