题目描述

给定一个有 $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$ 行以空格分隔的顺序输出路径中各顶点的编号，使它们形成一条路径。

样例 1

输入

5 6
1 3
1 4
2 3
1 5
3 5
2 4

输出

4
2 3 1 4

样例 2

输入

7 8
1 2
2 3
3 4
4 5
5 6
6 7
3 5
2 6

输出

7
1 2 3 4 5 6 7

样例 3

输入

12 18
3 5
4 12
9 11
1 10
2 5
6 10
8 11
1 3
4 10
2 4
3 7
2 10
3 12
3 9
1 7
2 3
2 11
10 11

输出

8
12 4 2 5 3 9 11 8

说明/提示

限制条件

• $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 翻译