配点 : 600 点
問題文
N 给出一棵顶点树。i 边的长度是 1 和顶点 u_i 与 边缘 v_i 连接。
頂点 1 开始,所有边都是 2 每次经过,顶点 想办法回到 1 。
i 第一个元素是 i 找到定义为所经过的顶点深度的最小可能词典顺序。然而,顶点的深度是 假设它指向 1 的距离。
制約
- 2 \leq N \leq 2\times 10^5
- 1 \leq u_i < v_i \leq N
- 给定的图是一棵树
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
出力
i 第一个元素是 i 输出尽可能小的字典顺序,定义为所经过的顶点的深度,以空格分隔。
入力例 1
4 1 2 2 3 1 4
出力例 1
0 1 0 1 2 1 0
頂点 1 →頂点 4 →頂点 1 →頂点 2 →頂点 3 →頂点 2 →頂点 1 ,深度序列按字典顺序是最小的。
入力例 2
2 1 2
出力例 2
0 1 0
入力例 3
6 2 5 3 5 1 4 4 5 4 6
出力例 3
0 1 2 1 2 3 2 3 2 1 0