#ABC168D. 洞窟重定向

洞窟重定向

题目描述

\hspace{15pt}一座洞窟有 nn 个房间、mm 条双向通道,房间编号为 1∼n1\sim n,房间 11 是出口。保证任意两个房间互相可达。

\hspace{15pt}请在每个非出口房间放置一块指示牌,指向与该房间直接相连的一个房间,使得从任意房间出发,始终按照指示牌移动,都能用最少步数到达房间 11。每经过一条通道计为一步。

\hspace{15pt}请判断方案是否存在,并输出任意一种合法方案。

输入格式

\hspace{15pt}第一行输入两个整数 $n,m\left(2\leqq n\leqq10^5;\ 1\leqq m\leqq2\times10^5\right)$。

\hspace{15pt}此后 mm 行,每行输入两个整数 $u_i,v_i\left(1\leqq u_i,v_i\leqq n;\ u_i\neq v_i\right)$,代表一条双向通道。

\hspace{15pt}保证输入的图连通。

输出格式

\hspace{15pt}若不存在合法方案,输出一行 "No"\texttt{"No"}。

\hspace{15pt}否则输出 nn 行,第一行输出 "Yes"\texttt{"Yes"};此后 n−1n-1 行,第 i−1i-1 行输出房间 i(2≦i≦n)i\left(2\leqq i\leqq n\right) 的指示牌指向的房间编号。

\hspace{15pt}存在多种方案时,输出任意一种即可。

测试样例

4 4
1 2
2 3
3 4
4 2
Yes
1
2
2

样例 1 解释

\hspace{15pt}房间 22 的指示牌指向 11,房间 3,43,4 的指示牌均指向 22。从三个房间到出口分别经过 1,2,21,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