分数: 600 点
问题陈述
我们有一棵树 N 顶点,已编号 1, 2, \dots, N。的 i第边缘 (1 \leq i \leq N-1) 连接顶点 A_i 和顶点 B_i.
一个男孩 E869120 发现了这棵树,并想在每个顶点写入一个整数,以让另一个男孩 square1001 感到惊讶。为此,需要满足以下条件,其中 E_i 是写在 Vertex 上的整数 i.
条件1: E_i \geq 1 (1 \leq i \leq N) 成立。
条件2: |E_i - E_j| \geq dist(i, j) 对于每对都成立 (i, j) (1 \leq i < j \leq N).
条件3: 值 \max(E_1, E_2, \dots, E_N) 应在满足条件 1 和 2 的同时最小化。
在这里, dist(i, j) 是:
- 从 Vertex 开始的简单路径(没有重复相同顶点的路径)的长度 i to j.
- 换句话说,它是值 L 简单路径在哪里 q_0 \to q_1 \to q_2 \to \cdots \to q_L (q_0 = i, q_L = j).
构造一种令 square1001 惊讶的整数写入方法。
约束
- 2 \leq N \leq 200000
- 1 \leq A_i < B_i \leq N
- 给定的图是一棵树。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
输出
打印包含整数的行 E_1, E_2, \cdots, E_N 按此顺序在顶点上书写,以空格作为分隔符。
如果有多种方法可以写入满足问题陈述中的条件的整数,则任何一种都将被接受。
E_1 E_2 \cdots E_{N}
示例输入 1
2 1 2
示例输出 1
2 1
如果我们写一个整数 顶点上的 2 在顶点上 1 和一个整数 1 在顶点上 2,我们有 dist(1, 2) = 1 和 |E_1 - E_2| = 1,满足条件2。
其他条件也满足了,所以我们可以这样给square1001一个惊喜。
(E_1, E_2) = (1, 2) 也将被接受。
示例输入 2
4 1 2 1 4 2 3
示例输出 2
3 2 1 4
(E_1, E_2, E_3, E_4) = (2, 3, 4, 1) 也将被接受。