AT_abc168_d [ABC168D] .. (Double Dots)

题目描述

在某个地方，有一个洞窟。

洞窟里有 $N$ 个房间和 $M$ 条通道，房间编号为 $1$ 到 $N$，通道编号为 $1$ 到 $M$。第 $i$ 条通道连接着房间 $A_i$ 和房间 $B_i$，且是双向的。任意两个房间之间都可以通过若干条通道互相到达。房间 $1$ 是洞窟入口的特殊房间。

由于洞窟内光线昏暗，决定在除房间 $1$ 以外的每个房间都设置一个“路标”。每个房间的路标会指向与该房间直接通过通道相连的某一个房间。

由于洞窟内部危险，希望对于除房间 $1$ 以外的每个房间，都满足以下条件：

• 从该房间出发，不断“查看当前房间的路标，并移动到路标所指的房间”，能够以最少的移动次数到达房间 $1$。

请判断是否存在一种满足目标的路标设置方法。如果存在，请输出其中一种方案。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$

输出格式

如果不存在满足目标的路标设置方法，输出 No。

如果存在，输出 $N$ 行。第 $1$ 行输出 Yes，第 $i$ 行（$2 \leq i \leq N$）输出房间 $i$ 的路标所指向的房间编号。

输入输出样例 #1

输入 #1

4 4
1 2
2 3
3 4
4 2

输出 #1

Yes
1
2
2

输入输出样例 #2

输入 #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

说明/提示

限制条件

• 所有输入均为整数。
• $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)$
• 任意两个房间之间都可以通过若干条通道互相到达。

样例解释 1

如输出样例所示设置路标时：

• 从房间 $2$ 出发，$(2) \to 1$，移动 $1$ 次，为最小值。
• 从房间 $3$ 出发，$(3) \to 2 \to 1$，移动 $2$ 次，为最小值。
• 从房间 $4$ 出发，$(4) \to 2 \to 1$，移动 $2$ 次，为最小值。

因此，按照输出样例设置路标即可满足目标。

样例解释 2

如果存在多种满足条件的方案，输出其中任意一种均可。

由 ChatGPT 4.1 翻译