問題文

\(N\) 頂点 \(M\) 辺の連結な無向グラフが与えられます。頂点には \(1\) から \(N\) まで番号がついており、与えられるグラフに多重辺や自己ループはありません。

以下の条件を満たすような長さ \(N\) の順列 \(p\) を1つ出力してください。

• 各 \(1 \leq i \leq N\) について、2頂点 \(i, p_i\) の距離 \(D(i, p_i)\)は 1 または 2 である。

条件を満たす順列は必ず存在することが証明できます。複数ある場合はどれを出力しても構いません。

2頂点\(u, v\)の距離 \(D(u, v)\)とは、頂点 \(u\) からグラフの辺をたどって頂点 \(v\) まで到達するパスのうち、パスに含まれる辺の数の最小値と定義されます。

制約

• \(2 \leq N \leq 200000\)
• \(N-1 \leq M \leq 200000\)
• \(1 \leq u_i, v_i \leq N\) (\(1 \leq i \leq M)\)
• 与えられるグラフにおいて頂点 \(u_i\), \(v_i\) を結ぶ無向辺 があることを示す。
• 入力から構成されるグラフは連結であり、多重辺および自己ループを含まない。
• 入力される値はすべて整数である。

入力例 1

2 1
1 2

出力例 1

2 1

2頂点の距離は \(D(1, 2) = D(2, 1) = 1\) であるため、条件を満たしています。

入力例 2

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

出力例 2

2 3 4 1

答えが複数考えられる場合は、どれを出力しても正解になります。