AT_abc240_e [ABC240E] Ranges on Tree

[problemUrl]: https://atcoder.jp/contests/abc240/tasks/abc240_e $ N $ 頂点の根付き木が与えられます。頂点 $ 1 $ が根です。 $ i\ =\ 1,\ 2,\ \ldots,\ N-1 $ について、$ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結んでいます。 $ i\ =\ 1,\ 2,\ \ldots,\ N $ について、頂点 $ i $ を根とする部分木に含まれる頂点全体からなる集合を $ S_i $ で表します。（各頂点は自身を根とする部分木に含まれます。すなわち、$ i\ \in\ S_i $ です。) また、整数 $ l,\ r $ について、$ l $ 以上 $ r $ 以下の整数全体からなる集合を $ [l,\ r] $ で表します。 すなわち、$ [l,\ r]\ =\ \lbrace\ l,\ l+1,\ l+2,\ \ldots,\ r\ \rbrace $ です。 整数の $ 2 $ つ組を $ N $ 個並べた列 $ \big((L_1,\ R_1),\ (L_2,\ R_2),\ \ldots,\ (L_N,\ R_N)\big) $ であって以下の条件を満たすものを考えます。 - $ 1\ \leq\ i\ \leq\ N $ を満たすすべての整数 $ i $ について、$ 1\ \leq\ L_i\ \leq\ R_i $ - $ 1\ \leq\ i,\ j\ \leq\ N $ を満たすすべての整数の組 $ (i,\ j) $ について次が成り立つ - $ S_i\ \subseteq\ S_j $ ならば、$ [L_i,\ R_i]\ \subseteq\ [L_j,\ R_j] $ - $ S_i\ \cap\ S_j\ =\ \emptyset $ ならば、$ [L_i,\ R_i]\ \cap\ [L_j,\ R_j]\ =\ \emptyset $ そのような $ \big((L_1,\ R_1),\ (L_2,\ R_2),\ \ldots,\ (L_N,\ R_N)\big) $ が少なくとも $ 1 $ つ存在することが示せます。 それらのうち、登場する整数の最大値 $ \max\ \lbrace\ L_1,\ L_2,\ \ldots,\ L_N,\ R_1,\ R_2,\ \ldots,\ R_N\ \rbrace $ が最小のものを $ 1 $ つ出力してください。（複数ある場合はどれを出力しても正解となります。）

入力は以下の形式で標準入力から与えられる。 > $ N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $

下記の形式で $ N $ 行出力せよ。すなわち、$ i\ =\ 1,\ 2,\ \ldots,\ N $ について、$ i $ 行目に $ L_i $ と $ R_i $ を空白区切りで出力せよ。 > $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_N $ $ R_N $

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ u_i,\ v_i\ \leq\ N $ - 入力はすべて整数 - 与えられるグラフは木である ### Sample Explanation 1 $ (L_1,\ R_1)\ =\ (1,\ 2),\ (L_2,\ R_2)\ =\ (2,\ 2),\ (L_3,\ R_3)\ =\ (1,\ 1) $ が問題文中の条件を満たします。 実際、$ [L_2,\ R_2]\ \subseteq\ [L_1,\ R_1],\ [L_3,\ R_3]\ \subseteq\ [L_1,\ R_1],\ [L_2,\ R_2]\ \cap\ [L_3,\ R_3]\ =\ \emptyset $ が成り立ちます。 また、$ \max\ \lbrace\ L_1,\ L_2,\ L_3,\ R_1,\ R_2,\ R_3\ \rbrace\ =\ 2 $ であり、これが最小です。