分数: 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
如果有多个解决方案,则接受其中任何一个。