AT_abc428_e [ABC428E] Farthest Vertex

頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点の木があります。 $ i $ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結ぶ辺です。 頂点 $ u $ と頂点 $ v $ の距離を、頂点 $ u $ と頂点 $ v $ を両端点とするパスに含まれる辺の本数として定義します。(このパスは一意に定まります) $ v = 1, 2, \dots, N $ について次の問題を解いてください。 - 頂点 $ 1, 2, \dots, N $ のうち頂点 $ v $ からの距離が最大となる頂点の番号を出力してください。ただし、条件を満たす頂点が複数存在する場合は **最も番号が大きい頂点** を出力してください。

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

$ N $ 行出力せよ。 $ i $ 行目には $ v=i $ の時の答えを出力せよ。

### Sample Explanation 1 頂点 $ 1 $ からの距離が最大となる点は頂点 $ 3 $ です。 頂点 $ 2 $ からの距離が最大となる点は頂点 $ 1 $ および頂点 $ 3 $ です。このうち番号が大きい頂点である頂点 $ 3 $ が答えとなります。 頂点 $ 3 $ からの距離が最大となる点は頂点 $ 1 $ です。 ### Constraints - $ 2 \leq N \leq 5 \times 10^5 $ - $ 1 \leq A_i \lt B_i \leq N $ - 入力で与えられるグラフは木 - 入力される値は全て整数