AT_arc211_d.[ARC211D] Michishirube

给定一个有 $N$ 个顶点和 $M$ 条边的简单连通无向图。第 $i$ 条边 $(1\leq i\leq M)$ 为无向边，连接顶点 $U_i$ 和 $V_i$。

请按如下规定在所有顶点上放置指示牌：

• 除顶点 $1$ 外，每个顶点放置一个蓝色指示牌，指向它的一个相邻顶点。
• 除顶点 $2$ 外，每个顶点放置一个黄色指示牌，指向它的一个相邻顶点。

同一顶点的两个指示牌指向的顶点不能是同一个。

判断是否存在一种指示牌的放置方式，使得满足以下条件，如果存在，输出其中一种方案：

• 从除顶点 $1$ 外的任意一个顶点出发，无限次沿着蓝色指示牌指向的顶点前进，最终必然到达顶点 $1$。
• 从除顶点 $2$ 外的任意一个顶点出发，无限次沿着黄色指示牌指向的顶点前进，最终必然到达顶点 $2$。

如果存在多种满足条件的放置方式，你可以输出其中任意一种。

输入以如下格式从标准输入给出：

$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$ 上蓝色指示牌指向的顶点的编号，以及黄色指示牌指向的顶点的编号。

如果存在多种方案，你可以输出其中任意一种。

样例解释 1

此处指示牌的放置方式如图所示。例如，从顶点 $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

不存在满足条件的指示牌放置方式。

约束条件

• $2\leq N\leq 2\times 10^5$
• $1\leq M\leq 3\times 10^5$
• $1\leq U_i < V_i\leq N$ 且 $1\leq i\leq M$
• 给定图保证简单且连通。
• 所有输入都是整数。

由 ChatGPT 5 翻译