题目描述

$N$ 頂点 $M$ 辺の、連結な単純無向グラフが与えられます。 頂点には $1$ から $N$ までの番号がついており、辺には $1$ から $M$ までの番号がついています。 辺 $i$ は、頂点 $A_i$ と頂点 $B_i$ を結んでいます。 次の条件を満たすパスを $1$ つ見つけて、出力してください。

• $2$ 個以上の頂点を通る
• 同じ頂点を $2$ 度以上通らない
• パスの少なくとも一方の端点と直接辺で結ばれている頂点は、必ずパスに含まれる

ただし、この問題の制約の下で、このようなパスが必ず存在することが証明できます。 また、あり得る答えのうちどれを出力しても構いません。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $:$ $A_M$ $B_M$

输出格式

条件を満たすパスを $1$ つ見つけて出力せよ。 出力の $1$ 行目には、パスに含まれる頂点の個数を出力せよ。 出力の $2$ 行目には、パスに含まれる頂点の番号を、パスを形成するような順序で、空白区切りにして出力せよ。

题目大意

给一张简单无向连通图，你需要找出一条满足以下条件的路径：

• 路径点数$\geq 2$
• 路径不经过相同的点
• 如果点$x$与路径的一个端点直接相连，那么$x$出现在路径中。

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

4
2 3 1 4

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

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$
• 与えられるグラフは連結かつ単純（どの $2$ 頂点を直接結ぶ辺も高々 $1$ つ）である

Sample Explanation 1

頂点 $2$ と直接辺で結ばれている頂点は、頂点 $3$ と $4$ です。 頂点 $4$ と直接辺で結ばれている頂点は、頂点 $1$ と $2$ です。 なので、$2$ → $3$ → $1$ → $4$ というパスは条件を満たします。