配点 : $400$ 点

問題文

AtCoder 国には $1$ から $N$ の番号がついた $N$ 個の都市と、$1$ から $N-1$ の番号がついた $N-1$ 個の道路があります。 道路 $i$ を通ると都市 $A_i$ と都市 $B_i$ の間を相互に移動することができます。全ての都市は道路を使って互いに行き来できることが保証されます。

高橋くんは都市 $1$ を出発し、次のルールで旅をします。

• いまいる都市と道路で直接つながっている都市のうち、まだ訪れたことがない都市が存在するとき、そのような都市のうち番号が最も小さい都市へ移動する
• そのような都市が存在しないとき- いまいる都市が都市 $1$ なら旅を終了する
  • そうでないなら、いまいる都市を初めて訪れたときに直前にいた都市へ移動する

高橋くんが旅の過程で訪れる都市を順に答えてください。

制約

• $2 \leq N \leq 2\times 10^5$
• $1\leq A_i,B_i \leq N$
• 全ての都市は道路を使って互いに行き来できる

入力

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

$N$

$A_1$ $B_1$

$\vdots$

$A_{N-1}$ $B_{N-1}$

出力

高橋くんが訪れる都市を、旅の開始時及び終了時の都市 $1$ も含めて順に空白区切りで出力せよ。

4
1 2
4 2
3 1

1 2 4 2 1 3 1

高橋くんの旅は次のようになります。

• 最初都市 $1$ にいます。
• 都市 $1$ から道路で直接つながっている都市のうち未訪問なのは都市 $2,3$ です。番号が小さい都市 $2$ へ移動します。
• 都市 $2$ から道路で直接つながっている都市のうち未訪問なのは都市 $4$ です。都市 $4$ へ移動します。
• 都市 $4$ から道路で直接つながっている都市のうち未訪問の都市はありません。直前にいた都市 $2$ へ移動します。
• 都市 $2$ から道路で直接つながっている都市のうち未訪問の都市はありません。初めて都市 $2$ に来る直前にいた都市 $1$ へ移動します。
• 都市 $1$ から道路で直接つながっている都市のうち未訪問なのは都市 $3$ です。都市 $3$ へ移動します。
• 都市 $3$ から道路で直接つながっている都市のうち未訪問の都市はありません。直前にいた都市 $1$ へ移動します。
• 都市 $1$ から道路で直接つながっている都市のうち未訪問の都市はありません。旅を終了します。

5
1 2
1 3
1 4
1 5

1 2 1 3 1 4 1 5 1