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$。

输入输出样例 #1

输入 #1

3 3
1 2
1 3
2 3

输出 #1

1
2
1

输入输出样例 #2

输入 #2

4 4
1 2
2 3
2 4
3 4

输出 #2

-1
2
3
2

输入输出样例 #3

输入 #3

5 10
1 2
1 4
1 5
2 1
2 3
3 1
3 2
3 5
4 2
4 3

输出 #3

1
1
3
1
1
1
1
1
1
1

输入输出样例 #4

输入 #4

4 1
1 2

输出 #4

-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 翻译