问题描述

我们有一个有 $N$ 个顶点的树，顶点编号为 $1, 2, \dots, N$。第 $i$ 条边 $(1 \leq i \leq N-1)$ 连接顶点 $A_i$ 和顶点 $B_i$。

一个名叫 E869120 的男孩发现了这棵树，并希望在每个顶点上写一个整数来给另一个名叫 square1001 的男孩一个惊喜。为此，需要满足以下条件，其中 $E_i$ 是写在顶点 $i$ 上的整数。

**条件 1：**对于所有的 $i$ $(1 \leq i \leq N)$，都有 $E_i \geq 1$。
**条件 2：**对于所有的 $(i, j)$ $(1 \leq i < j \leq N)$，都有 $|E_i - E_j| \geq \text{dist}(i, j)$。
**条件 3：**在满足条件 1 和条件 2 的前提下，最大值 $\max(E_1, E_2, \dots, E_N)$ 应该被最小化。

这里，$\text{dist}(i, j)$ 是：

• 从顶点 $i$ 到顶点 $j$ 的简单路径的长度（不经过重复顶点的路径）。
• 换句话说，它是简单路径 $q_0 \to q_1 \to q_2 \to \dots \to q_L$（其中 $q_0 = i, q_L = j$）的值 $L$。

构建一种写整数的方法，给 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, \dots, E_N$ 的行。

如果有多种满足问题描述中条件的写整数的方法，则任何一种方法都被接受。

$E_1$ $E_2$ $\cdots$ $E_{N}$

示例输入 1

2
1 2

示例输出 1

2 1

如果我们在顶点 1 上写整数 2，顶点 2 上写整数 1，我们有 $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)$ 也可以被接受。