配点 : $500$ 点

問題文

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

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

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

制約

• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq A_i < B_i \leq N$
• 与えられるグラフは連結かつ単純（どの $2$ 頂点を直接結ぶ辺も高々 $1$ つ）である

入力

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

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$:$

$A_M$ $B_M$

出力

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

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

4
2 3 1 4

頂点 $2$ と直接辺で結ばれている頂点は、頂点 $3$ と $4$ です。 頂点 $4$ と直接辺で結ばれている頂点は、頂点 $1$ と $2$ です。 なので、$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