.. (Double Dots)

题目描述

有一个洞穴。 洞穴有 $N$ 个房间和 $M$ 条通道。房间编号为 $1$ 到 $N$，通道编号为 $1$ 到 $M$。通道 $i$ 双向连接房间 $A_i$ 和房间 $B_i$。可以通过通道在任意两个房间之间行走。房间 $1$ 是一个有外部入口的特殊房间。 洞穴里很黑，所以我们决定在除房间 $1$ 之外的每个房间里放一个指示牌。每个房间里的指示牌将指向与该房间通过通道直接相连的某个房间。 由于洞穴很危险，我们的目标是满足下述对除房间 $1$ 之外每个房间的条件。

如果你从该房间出发，并反复移动到你所在房间里的指示牌所指示的房间，那么你将在经过最少数量的通道后到达房间 $1$。

确定是否存在放置指示牌以满足我们的目标的方案，如果存在则输出一种这样的方案。

输入格式

输入从标准输入给出，格式如下： $N$ $M$ $A_1$ $B_1$ : $A_M$ $B_M$

输出格式

如果不存在满足目标的放置指示牌的方案，输出 $No$。 否则，输出 $N$ 行。第一行应包含 $Yes$，第 $i$ 行 $(2 \leq i \leq N)$ 应包含表示房间 $i$ 中指示牌所指房间的整数。

4 4
1 2
2 3
3 4
4 2

Yes
1
2
2

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

Yes
6
5
5
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)$ 可以通过通道在任意两个房间之间行走。如果我们按样例输出所示放置指示牌，情况如下：

从房间 $2$ 出发，你将在经过一条通道后到达房间 $1$：$(2) \to 1$。这是可能的最少通道数。 从房间 $3$ 出发，你将在经过两条通道后到达房间 $1$：$(3) \to 2 \to 1$。这是可能的最少通道数。 从房间 $4$ 出发，你将在经过两条通道后到达房间 $1$：$(4) \to 2 \to 1$。这是可能的最少通道数。

因此，该目标被满足。
如果存在多个解，则接受任意一个。

标签: AtCoder|abc168D

来源

AtCoder|abc168D