← 返回题目列表

AtCoder · nadafes2022_day1_l

L. 词典学欧拉之旅

中文机器翻译题面 查看原题

配点 : 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