← 返回题目列表

AtCoder · agc013_b

B. 哈密顿路径

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

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