AT_arc183_d [ARC183D] Keep Perfectly Matched

[problemUrl]: https://atcoder.jp/contests/arc183/tasks/arc183_d $ 1 $ から $ N $ までの番号のついた $ N $ 頂点からなる木があります． $ i $ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結ぶ辺です． ここで $ N $ は偶数で，さらにこの木は完全マッチングを持ちます． 具体的には，各 $ i $ ($ 1\ \leq\ i\ \leq\ N/2 $) に対し，$ A_i=i\ \times\ 2-1,B_i=i\ \times\ 2 $ が保証されます． あなたは以下の操作を $ N/2 $ 回行います． - 葉 (次数がちょうど $ 1 $ の頂点) を $ 2 $ つ選び，木から削除する． ただしここで，削除したあとの木も完全マッチングを持つ必要がある． なお，この問題では頂点が $ 0 $ 個の場合も木と呼ぶことにする． 各操作について，そのスコアを「選んだ $ 2 $ つの頂点の間の距離 (その $ 2 $ つの頂点を結ぶ単純パス上の辺の個数) 」とします． スコアの合計を最大化するような手順を $ 1 $ つ示してください． なお，この問題の制約下で $ N/2 $ 回の操作を完了する手順が常に存在することが証明できます．

入力は標準入力から以下の形式で与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $

答えを以下の形式で出力せよ． > $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_{N/2} $ $ Y_{N/2} $ ここで，$ X_i,Y_i $ は $ i $ 回目の操作で選ぶ $ 2 $ つの頂点である． 解が複数存在する場合，どれを出力しても構わない．

### 制約 - $ 2\ \leq\ N\ \leq\ 250000 $ - $ N $ は偶数 - $ 1\ \leq\ A_i\