C - Permutation City /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : \(200\) 点

問題文

\(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\) を結ぶ無向辺 があることを示す。
  • 入力から構成されるグラフは連結であり、多重辺および自己ループを含まない。
  • 入力される値はすべて整数である。

入力

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

\(N\) \(M\)
\(u_1\) \(v_1\)
\(u_2\) \(v_2\)
\(\vdots\)
\(u_M\) \(v_M\)

出力

条件を満たす順列 \(p\) をスペース区切りで出力せよ。


入力例 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

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