問題文

N 頂点の木が与えられます。頂点には 1 から N までの番号が付けられており、i 番目の辺 (1 \leq i \leq N-1) は頂点 A_i と B_i を接続しています。

この木から、どの頂点も隣り合わないように、重複しない \frac{N}{2} 頂点を取り出してください。

制約

• 2 \leq N \leq 10^5
• 1 \leq A_i < B_i \leq N
• N は偶数
• 入力は全て整数
• 与えられるデータは木である

入力例 1

4
1 2
2 3
2 4

出力例 1

3 4

入力例 2

6
1 3
2 4
3 5
2 5
3 6

出力例 2

1 2 6