当前没有测试数据。

F - 传送门设置

得分：500分

问题描述

有N个编号从Town1到TownN的城镇。
还有M个传送门，每个传送门都是双向的，可以以1分钟的速度从一个城镇到达另一个城镇。

第i个传送门连接了TownUi和TownVi。
然而，对于某些传送门，连接的一个城镇是未确定的； $U_i=0$意味着第i个传送门连接的一个城镇是TownVi， 但是另一个端点是未确定的。

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

当所有未确定端点的传送门确定连接到Towni时， 从Town1到TownN最少需要多少分钟？ 如果仅依靠传送门无法从Town1到达TownN，则输出$-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$和$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$时的答案。

3 2
0 2
1 2

-1 -1 2

当所有未确定端点的传送门都确定连接到Town1时，
第1个和第2个传送门都连接了Town1和Town2。 那么，无法从Town1到达Town3。

当所有未确定端点的传送门都确定连接到Town2时，
第1个传送门连接了Town2和它自己，第2个传送门连接了Town1和Town2。 同样，无法从Town1到达Town3。

当所有未确定端点的传送门都确定连接到Town3时，
第1个传送门连接了Town3和Town2，第2个传送门连接了Town1和Town2。 在这种情况下，我们可以在2分钟内从Town1到达Town3。

• 使用第2个传送门从Town1到Town2。
• 使用第1个传送门从Town2到Town3。

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

请注意，取决于未确定端点的传送门连接到哪个城镇，可能会有一个传送门连接一个城镇和它自己， 或者有多个传送门连接同一对城镇。

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

3 3 3 3 2