← 返回题目列表

AtCoder · abc168_d

D. ..(双点)

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

分数: 400 点

问题陈述

有一个山洞。

洞穴里有 N 房间和 M 段落。房间有编号 1 to N,并且段落已编号 1 to M。通道 i 连接房间 A_i 和房间 B_i 双向。一个人可以通过穿过通道在任意两个房间之间移动。房间 1 是一个特殊的房间,有一个从外面进入的房间。

洞里很黑,所以我们决定在除了Room之外的每个房间都放置一个路标 1。每个房间的路标将指向其中一个房间,该房间通过通道直接与该房间相连。

由于山洞里很危险,我们的目标是除了房间之外的每个房间都满足以下条件 1.

  • 如果你从那个房间开始并反复移动到你所在房间的路标指示的房间,你将到达房间 1 遍历尽可能少的通道数后。

确定是否有一种方法可以放置满足我们目标的路标,如果存在,则打印一种这样的方法。

约束

  • 输入中的所有值都是整数。
  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N\ (1 \leq i \leq M)
  • A_i \neq B_i\ (1 \leq i \leq M)
  • 一个人可以通过穿越通道在任意两个房间之间移动。

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1
:
A_M B_M

输出

如果无法放置满足目标的路标,请打印 No.

否则,打印 N 行。第一行应包含 Yes,以及 i第行 (2 \leq i \leq N) 应包含代表 Room 中路标指示的房间的整数 i.


示例输入 1

4 4
1 2
2 3
3 4
4 2

示例输出 1

Yes
1
2
2

如果我们按照示例输出中的描述放置路标,则会发生以下情况:

  • 从房间开始 2,您将到达房间 1 遍历完一段后: (2) \to 1。这是可能的最小通道数。
  • 从房间开始 3,您将到达房间 1 遍历两段后: (3) \to 2 \to 1。这是可能的最小通道数。
  • 从房间开始 4,您将到达房间 1 遍历两段后: (4) \to 2 \to 1。这是可能的最小通道数。

因此,达到了目的。


示例输入 2

6 9
3 4
6 1
2 4
5 3
4 6
1 5
6 2
4 5
5 6

示例输出 2

Yes
6
5
5
1
1

如果有多个解决方案,则接受其中任何一个。