← 返回题目列表

AtCoder · arc211_d

D. 道标部

中文机器翻译题面 查看原题

分数: 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

无法放置满足条件的路标。