分数: 700 点
问题陈述
给你一个简单的连通无向图 N 顶点和 M 边缘。的 i第边缘 (1\leq i\leq M) 是连接顶点的无向边 U_i 和 V_i.
在所有顶点放置路标,如下所示:
- 在除顶点之外的每个顶点 1,放置一个指向其相邻顶点之一的蓝色路标。
- 在除顶点之外的每个顶点 2,放置一个指向其相邻顶点之一的黄色路标。
这里,同一顶点的两个路标不能指向同一顶点。
判断是否可以放置满足以下条件的路标,如果可以,输出一种放置方式:
- 从顶点以外的任何顶点 1,你可以到达顶点 1 重复移动到蓝色路标指向的顶点有限次。
- 从顶点以外的任何顶点 2,你可以到达顶点 2 重复移动到黄色路标指向的顶点有限次。
如果有多种放置满足条件的路标的方法,则可以输出其中任何一种。
约束
- 2\leq N\leq 2\times 10^5
- 1\leq M\leq 3\times 10^5
- 1\leq U_i\lt V_i\leq N (1\leq i\leq M)
- 给定的图很简单且连通。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M U_1 V_1 U_2 V_2 \vdots U_M V_M
输出
如果没有办法放置满足条件的路标,则输出
仅 No 。
如果有,则输出 N+1 行。
第一行应包含 Yes.
第二行应包含顶点处黄色路标所指向的顶点编号 1.
第三行应包含顶点处蓝色路标所指向的顶点的编号 2.
的 i第行 (4\leq i\leq N+1) 应包含顶点处蓝色路标所指向的顶点的编号 i-1 以及顶点处黄色路标所指向的顶点编号 i-1,按此顺序,用空格分隔。
如果有多个解,则可以输出其中任何一个。
示例输入 1
7 8 1 3 3 4 4 5 1 5 4 6 2 6 2 7 4 7
示例输出 1
Yes 5 6 4 1 5 6 1 4 4 2 4 2
这里,路标的放置如下图所示。例如,从顶点 3:
- 沿着蓝色路标,您作为顶点移动 3\rightarrow 4\rightarrow 5\rightarrow 1,最终到达顶点 1.
- 沿着黄色路标,您作为顶点移动 3\rightarrow 1\rightarrow 5\rightarrow 4 \rightarrow 6\rightarrow 2,最终到达顶点 2.
您还可以验证是否遵循来自顶点的蓝色路标 2 通向顶点 1,然后沿着顶点的黄色路标 1 通向顶点 2。其他顶点也满足条件。

还有多种其他解决方案,但顶点处不能同时有蓝色路标和黄色路标 3 指向顶点 4,因为同一顶点的路标将指向同一顶点。
示例输入 2
10 12 1 3 3 4 4 5 1 5 4 6 2 6 2 7 4 7 4 8 8 9 9 10 8 10
示例输出 2
No
无法放置满足条件的路标。