AT_abc240_e.[ABC240E] Ranges on Tree

题面简述

给出一个有 $N$ 个节点的树和其中的 $N-1$ 条树边（描述无向），其中我们规定节点编号为 $1,2,\cdots,N-1,N$，其中节点 $1$ 为树根。

你需要给予每一个节点 $i$ 一个闭区间 $[L_i,R_i]$，你需要保证一下性质。

• 虽然当 $L_i=R_i$ 的时候不满足闭区间书写规范，但是在本题中允许出现。

• $\forall_i,1\le L_i\le R_i$。

• 如果 $i$ 是 $j$ 的父亲节点，保证 $[L_j,R_j]\subseteq [L_i,R_i]$。

• 如果 $i,j$ 为兄弟节点（拥有相同的父亲节点），那么保证 $[L_i,R_i]\cap[L_j,R_j]=\varnothing$。

你需要保证你构造出的方案的 $\max\limits_{i=1}^{N} R_i$ 最小。

如以下形式输入。

$ N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $

如一下形式输出，对于每一组 $L_i$ 与 $R_i$ 之间需要空格，不同组之间用换行分开。

$ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_N $ $ R_N $

@qingshu 译。