← 返回题目列表

AtCoder · abc257_f

I. 传送器设置

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N 城镇 编号城镇 1, 镇 2, \ldots, 镇 N.
还有 M 传送器,每个城镇都双向连接两个城镇,这样一个人可以在一分钟内从一个城镇到达另一个城镇。

的 i-th 传送器连接城镇 U_i 和镇 V_i 双向。 然而,对于一些传送器来说,它所连接的城镇之一是不确定的; U_i=0 表示该城镇之一 i-第一个传送器连接的是城镇 V_i, 但另一端未定。

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

当末端未确定的传送器全部确定连接到城镇时 i, 从 镇 出发 至少需要多少分钟 1 到镇 N? 如果无法从城镇出发 1 to 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
  • If 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-st 和 2-nd 传送器都连接城镇 1 和 2。 那么,就不可能从城镇出发了 1 到镇 3.

当未确定末端的传送器全部确定连接到城镇时 2,
这 1-st 传送器连接城镇 2 和它本身,以及 2- 第一个连接城镇 1 和 2。 再次强调,从城镇出发是不可能的 1 到镇 3.

当未确定末端的传送器全部确定连接到城镇时 3,
这 1-st 传送器连接城镇 3 和镇 2,以及 2- 第一个连接城镇 1 和 2。 在这种情况下,我们可以从 Town 出发 两分钟内 1 到镇 3 。

  • 使用 2-nd 传送器从城镇出发 1 到镇 2.
  • 使用 1-st 传送器从城镇出发 2 到镇 3.

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

请注意,根据末端未确定的传送器连接到哪个城镇, 可能有一个传送器连接一个城镇和它本身, 或连接同一对城镇的多个传送器。


示例输入 2

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

示例输出 2

3 3 3 3 2