传送门设置

题目描述

有 $N$ 个城镇，编号为城镇 1、城镇 2、……、城镇 $N$。

还有 $M$ 个传送门，每个传送门双向连接两个城镇，可以在 1 分钟内从一端到达另一端。

第 $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
⋮
U_M V_M

输出格式

输出 $N$ 个整数，以空格分隔。 其中第 $k$ 个整数是 $i=k$ 时上述问题的答案。

样例

3 2
0 2
1 2

-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。 此时可以在 2 分钟内从城镇 1 到达城镇 3。

使用第 2 个传送门从城镇 1 到城镇 2。

使用第 1 个传送门从城镇 2 到城镇 3。

因此，应按顺序输出 $-1,-1,2$。

注意，根据端未确定的传送门连接到哪个城镇的不同， 可能出现连接同一城镇自身的传送门， 也可能出现连接同一对城镇的多个传送门。

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

3 3 3 3 2

数据范围

• $2 \le N \le 3 \times 10^5$
• $1 \le M \le 3 \times 10^5$
• $0 \le U_i \lt V_i \le N$
• 若 $i \neq j$，则 $(U_i, V_i) \neq (U_j, V_j)$。
• 输入中的所有值均为整数。