AT_abc257_f [ABC257F] Teleporter Setting

题目描述

有 $N$ 个城镇和 $M$ 个传送器，城镇编号为 $1, 2, \ldots, N$。
每个传送器可以双向连接两个城镇，使用传送器可以在 $1$ 分钟内从一个城镇移动到另一个城镇。

第 $i$ 个传送器连接城镇 $U_i$ 和城镇 $V_i$，但有些传送器连接的其中一个城镇尚未确定。如果 $U_i=0$，则表示该传送器的一端连接城镇 $V_i$，另一端尚未确定。

对于 $i=1,2,\ldots,N$，请分别解决以下问题：

将所有连接端未定的传送器的未定端都连接到城镇 $i$。此时，从城镇 $1$ 到城镇 $N$ 最少需要多少分钟？如果仅使用传送器无法从城镇 $1$ 到达城镇 $N$，请输出 $-1$。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$

输出格式

请输出 $N$ 个整数，空格分隔。第 $k$ 个整数表示当所有未定端都连接到城镇 $k$ 时，从城镇 $1$ 到城镇 $N$ 的最短所需时间。

输入输出样例 #1

输入 #1

3 2
0 2
1 2

输出 #1

-1 -1 2

输入输出样例 #2

输入 #2

5 5
1 2
1 3
3 4
4 5
0 2

输出 #2

3 3 3 3 2

说明/提示

限制条件

• $2 \leq N \leq 3\times 10^5$
• $1 \leq M \leq 3\times 10^5$
• $0 \leq U_i < V_i \leq N$
• 若 $i \neq j$，则 $(U_i, V_i) \neq (U_j, V_j)$
• 输入均为整数

样例解释 1

当所有未定端都连接到城镇 $1$ 时，第 $1$ 个和第 $2$ 个传送器都连接城镇 $1$ 和城镇 $2$。此时无法从城镇 $1$ 到达城镇 $3$。

当所有未定端都连接到城镇 $2$ 时，第 $1$ 个传送器连接城镇 $2$ 自身，第 $2$ 个传送器连接城镇 $1$ 和城镇 $2$。此时也无法从城镇 $1$ 到达城镇 $3$。

当所有未定端都连接到城镇 $3$ 时，第 $1$ 个传送器连接城镇 $3$ 和城镇 $2$，第 $2$ 个传送器连接城镇 $1$ 和城镇 $2$。此时可以按如下方式用 $2$ 分钟从城镇 $1$ 到达城镇 $3$：

• 使用第 $2$ 个传送器从城镇 $1$ 到城镇 $2$。
• 使用第 $1$ 个传送器从城镇 $2$ 到城镇 $3$。

因此，依次输出 $-1,-1,2$。

请注意，可能存在连接同一城镇的传送器，或存在多个传送器连接同一对城镇。

由 ChatGPT 4.1 翻译