分数: 500 点
问题陈述
给你一个连通的无向简单图,其中有 N 顶点和 M 边缘。 顶点已编号 1 通过 N,并且边缘已编号 1 通过 M。 边缘 i 连接顶点 A_i 和 B_i。 你的任务是找到满足以下条件的路径:
- 路径遍历两个或多个顶点。
- 路径不会多次遍历同一顶点。
- 直接连接到路径的至少一个端点的顶点始终包含在路径中。
可以证明这样的路径总是存在的。 此外,如果有多个解决方案,则其中任何一个都将被接受。
约束
- 2 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq A_i < B_i \leq N
- 给定的图是连通且简单的(即,对于每对顶点,最多有一条边直接连接它们)。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 A_2 B_2 : A_M B_M
输出
找到一条满足条件的路径,并按如下格式打印。 在第一行中,打印路径中包含的顶点数。 在第二行中,按照路径中出现的顺序打印以空格分隔的顶点索引列表。
示例输入 1
5 6 1 3 1 4 2 3 1 5 3 5 2 4
示例输出 1
4 2 3 1 4
有两个顶点直接连接到顶点 2:顶点 3 和 4。 还有两个顶点直接连接到顶点 4:顶点 1 和 2。 因此,路径 2 → 3 → 1 → 4 满足条件。
示例输入 2
7 8 1 2 2 3 3 4 4 5 5 6 6 7 3 5 2 6
示例输出 2
7 1 2 3 4 5 6 7