Teleporter Setting

题目描述

有 $N$ 个城镇 编号为 城镇 $1$, 城镇 $2$, $\ldots$, 城镇 $N$.
还有 $M$ 个瞬移器，每个瞬移器双向连接两个城镇，使得一个人可以在一分钟内从一个城镇到达另一个城镇。 第 $i$ 个瞬移器双向连接 城镇 $U_i$ 和 城镇 $V_i$。 然而，对于其中一些瞬移器，它所连接的其中一个城镇尚未确定； $U_i=0$ 表示第 $i$ 个瞬移器连接的一个城镇是 城镇 $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$ 个整数应当是在 $i=k$ 时问题的答案。

3 2
0 2
1 2

-1 -1 2

5 5
1 2
1 3
3 4
4 5
0 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$ 个和第 $2$ 个瞬移器都连接 城镇 $1$ 和 城镇 $2$。 此时，无法从 城镇 $1$ 旅行到 城镇 $3$。 当所有端点未确定的瞬移器都被确定为连接到 城镇 $2$ 时，
第 $1$ 个瞬移器连接 城镇 $2$ 和 它自身，第 $2$ 个瞬移器连接 城镇 $1$ 和 城镇 $2$。 同样地，无法从 城镇 $1$ 旅行到 城镇 $3$。 当所有端点未确定的瞬移器都被确定为连接到 城镇 $3$ 时，
第 $1$ 个瞬移器连接 城镇 $3$ 和 城镇 $2$，第 $2$ 个瞬移器连接 城镇 $1$ 和 城镇 $2$。 在这种情况下，我们可以在两分钟内从 城镇 $1$ 旅行到 城镇 $3$。

使用第 $2$ 个瞬移器从 城镇 $1$ 到 城镇 $2$。 使用第 $1$ 个瞬移器从 城镇 $2$ 到 城镇 $3$。

因此，应当按此顺序输出 $-1,-1$ 和 $2$。 注意，取决于那些端点未确定的瞬移器被连接到哪个城镇， 可能会有连接某城镇自身的瞬移器， 或多个瞬移器连接相同的一对城镇。

标签: AtCoder|abc257F

来源

AtCoder|abc257F