AT_agc013_b [AGC013B] Hamiltonish Path

给定一个有 $N$ 个顶点和 $M$ 条边的连通简单无向图。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边连接了顶点 $A_i$ 和顶点 $B_i$。请找到并输出一个满足以下条件的路径： - 路径经过不少于 $2$ 个顶点。 - 路径不经过同一顶点超过一次。 - 至少包含路径两端点之一的所有直接相连的顶点。 在本题给定的约束下，可以证明总是存在这样的路径。你可以输出所有可能解中的任意一个。

输入通过标准输入给出，格式如下： > $N\ M\ A_1\ B_1\ A_2\ B_2\ :\ A_M\ B_M$

请输出一个满足条件的路径。 输出第 $1$ 行包含路径中顶点的个数。 输出第 $2$ 行以空格分隔的顺序输出路径中各顶点的编号，使它们形成一条路径。

## 限制条件 - $2\leq N \leq 10^5$ - $1\leq M \leq 10^5$ - $1\leq A_i < B_i \leq N$ - 所给的图是连通且简单的（任意两点之间最多只有一条直接连边）。 ## 样例解释 1 与顶点 $2$ 直接相连的顶点是 $3$ 和 $4$。与顶点 $4$ 直接相连的顶点是 $1$ 和 $2$。所以，$2$ → $3$ → $1$ → $4$ 这条路径符合所有条件。 由 ChatGPT 5 翻译