双点

题目描述

某处有一个洞穴。

洞穴里有 $N$ 个房间和 $M$ 条通道,房间编号为 $1$ 到 $N$,通道编号为 $1$ 到 $M$。通道 $i$ 双向连接房间 $A_i$ 和房间 $B_i$。任意两个房间之间都可以通过若干条通道往返。房间 $1$ 是设有洞穴入口的特殊房间。

由于洞穴内光线昏暗,决定在除房间 $1$ 外的每个房间里各设置 $1$ 个路标。每个房间的路标指向与该房间通过通道直接相连的某个房间。

洞穴内很危险,因此目标是使除房间 $1$ 外的每个房间都满足以下条件:

• 从该房间出发,重复「查看当前所在房间的路标,移动到它所指向的房间」这一过程,能以最少的移动次数到达房间 $1$。

请判断是否存在能达成目标的路标摆放方案,若存在,输出其中的一种。

输入格式

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

$N$ $M$
$A_1$ $B_1$
$:$
$A_M$ $B_M$

输出格式

若不存在能达成目标的路标摆放方案,输出 No。

若存在,输出 $N$ 行。第 $1$ 行输出 Yes,第 $i\ (2 \leq i \leq N)$ 行输出房间 $i$ 的路标所指向的房间编号。

样例

4 4
1 2
2 3
3 4
4 2

Yes
1
2
2

按输出示例摆放路标时:

• 从房间 $2$ 出发时,移动 $(2) \to 1$ 共 $1$ 次,这是最少的。
• 从房间 $3$ 出发时,移动 $(3) \to 2 \to 1$ 共 $2$ 次,这是最少的。
• 从房间 $4$ 出发时,移动 $(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

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)$
• 任意两个房间之间都可以通过若干条通道往返

提示

答案不唯一,输出任意合法解即可。