#ABC168D. 洞窟重定向
洞窟重定向
题目描述
一座洞窟有 个房间、 条双向通道,房间编号为 ,房间 是出口。保证任意两个房间互相可达。
请在每个非出口房间放置一块指示牌,指向与该房间直接相连的一个房间,使得从任意房间出发,始终按照指示牌移动,都能用最少步数到达房间 。每经过一条通道计为一步。
请判断方案是否存在,并输出任意一种合法方案。
输入格式
第一行输入两个整数 $n,m\left(2\leqq n\leqq10^5;\ 1\leqq m\leqq2\times10^5\right)$。
此后 行,每行输入两个整数 $u_i,v_i\left(1\leqq u_i,v_i\leqq n;\ u_i\neq v_i\right)$,代表一条双向通道。
保证输入的图连通。
输出格式
若不存在合法方案,输出一行 。
否则输出 行,第一行输出 ;此后 行,第 行输出房间 的指示牌指向的房间编号。
存在多种方案时,输出任意一种即可。
测试样例
4 4
1 2
2 3
3 4
4 2
Yes
1
2
2
样例 1 解释
房间 的指示牌指向 ,房间 的指示牌均指向 。从三个房间到出口分别经过 步,均为最短距离。
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