102575: [AtCoder]ABC257 F - Teleporter Setting

Problem Statement

There are $N$ towns numbered Town $1$, Town $2$, $\ldots$, Town $N$.
There are also $M$ Teleporters, each of which connects two towns bidirectionally so that a person can travel from one to the other in one minute.

The $i$-th Teleporter connects Town $U_i$ and Town $V_i$ bidirectionally. However, for some of the Teleporters, one of the towns it connects is undetermined; $U_i=0$ means that one of the towns the $i$-th Teleporter connects is Town $V_i$, but the other end is undetermined.

For $i=1,2,\ldots,N$, answer the following question.

When the Teleporters with undetermined ends are all determined to be connected to Town $i$, how many minutes is required at minimum to travel from Town $1$ to Town $N$? If it is impossible to travel from Towns $1$ to $N$ using Teleporters only, print $-1$ instead.

Constraints

• $2 \leq N \leq 3\times 10^5$
• $1\leq M\leq 3\times 10^5$
• $0\leq U_i<V_i\leq N$
• If $i \neq j$, then $(U_i,V_i)\neq (U_j,V_j)$.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print $N$ integers, with spaces in between. The $k$-th integer should be the answer to the question when $i=k$.

Sample Input 1

3 2
0 2
1 2

Sample Output 1

-1 -1 2

When the Teleporters with an undetermined end are all determined to be connected to Town $1$,
the $1$-st and the $2$-nd Teleporters both connect Towns $1$ and $2$. Then, it is impossible to travel from Town $1$ to Town $3$.

When the Teleporters with an undetermined end are all determined to be connected to Town $2$,
the $1$-st Teleporter connects Town $2$ and itself, and the $2$-nd one connects Towns $1$ and $2$. Again, it is impossible to travel from Town $1$ to Town $3$.

When the Teleporters with an undetermined end are all determined to be connected to Town $3$,
the $1$-st Teleporter connects Town $3$ and Town $2$, and the $2$-nd one connects Towns $1$ and $2$. In this case, we can travel from Town $1$ to Town $3$ in two minutes.

• Use the $2$-nd Teleporter to travel from Town $1$ to Town $2$.
• Use the $1$-st Teleporter to travel from Town $2$ to Town $3$.

Therefore, $-1,-1$, and $2$ should be printed in this order.

Note that, depending on which town the Teleporters with an undetermined end are connected to, there may be a Teleporter that connects a town and itself, or multiple Teleporters that connect the same pair of towns.

Sample Input 2

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

Sample Output 2

3 3 3 3 2

问题描述

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

第 $i$ 个传送器双向连接城镇 Town $U_i$ 和 Town $V_i$。但是，对于某些传送器，它连接的城镇之一是不确定的； $U_i=0$ 表示第 $i$ 个传送器连接的城镇之一是 Town $V_i$，但另一端是不确定的。

对于 $i=1,2,\ldots,N$，回答以下问题。

当所有具有不确定端点的传送器都确定连接到城镇 $i$ 时，从 Town $1$ 到 Town $N$ 最少需要多少分钟？ 如果无法仅使用传送器从 Towns $1$ 到 $N$ 旅行，则打印 $-1$ 而不是。

约束

• $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)$。
• 输入中的所有值都是整数。

输入

输入将从标准输入中以以下格式给出：

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

输出

打印 $N$ 个整数，之间用空格隔开。 第 $k$ 个整数应该是当 $i=k$ 时问题的答案。

样例输入 1

3 2
0 2
1 2

样例输出 1

-1 -1 2

当具有不确定端点的传送器都被确定连接到城镇 $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$。

注意，取决于具有不确定端点的传送器连接到哪个城镇，可能存在一个传送器连接一个城镇和自身，或者多个传送器连接相同的一对城镇。

样例输入 2

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

样例输出 2

3 3 3 3 2