题目描述

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

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

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

当不确定末端的传送器都确定连接到 Town $i$ 时，从 Town $1$ 到 Town $N$ 最少需要多少分钟？如果只使用传送器无法从 Town $1$ 到 Town $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

当不确定末端的传送器都确定连接到 Town $1$ 时， 第 $1$ 个和第 $2$ 个传送器都连接 Town $1$ 和 Town $2$。那么，从 Town $1$ 到 Town $3$ 是不可能的。

当不确定末端的传送器都确定连接到 Town $2$ 时， 第 $1$ 个传送器连接 Town $2$ 和自身，第 $2$ 个传送器连接 Town $1$ 和 Town $2$。同样，从 Town $1$ 到 Town $3$ 是不可能的。

当不确定末端的传送器都确定连接到 Town $3$ 时， 第 $1$ 个传送器连接 Town $3$ 和 Town $2$，第 $2$ 个传送器连接 Town $1$ 和 Town $2$。在这种情况下，我们可以在两分钟内从 Town $1$ 到 Town $3$。

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

因此，应按顺序打印 $-1,-1$ 和 $2$。

注意，根据不确定末端的传送器连接到哪个城镇，可能有一个连接到自身的传送器，或者多个连接到同一对城镇的传送器。

示例输入2

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

示例输出2

3 3 3 3 2