题目描述

有一棵包含 $N$ 个顶点的树，顶点编号为 $1, 2, \dots, N$。第 $i$ 条边（$1 \leq i \leq N-1$）连接顶点 $A_i$ 和顶点 $B_i$。

E869120 君发现了这棵树，想在每个顶点上写一个整数，以此来让 square1001 君感到惊讶。为了达到这个目的，设在顶点 $i$ 上写的整数为 $E_i$，需要满足以下条件：

条件 1 对于所有 $1 \leq i \leq N$，都有 $E_i \geq 1$。

条件 2 对于所有的 $1 \leq i < j \leq N$，都有 $|E_i - E_j| \geq dist(i, j)$。

条件 3 在满足条件 1 和条件 2 的所有方案中，使 $\max(E_1, E_2, \dots, E_N)$ 的值最小。

其中，$dist(i, j)$ 表示：

• 从顶点 $i$ 到顶点 $j$ 的简单路径（不经过重复顶点的路径）的长度。
• 即，若简单路径为 $q_0 \to q_1 \to q_2 \to \cdots \to q_L$（$q_0 = i, q_L = j$），则 $dist(i, j) = L$。

请构造一种整数的写法，使得 square1001 君会感到惊讶。

输入格式

输入以如下格式从标准输入读入。

$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

输出

2 1

样例 2

输入

4
1 2
1 4
2 3

输出

3 2 1 4

说明/提示

数据范围

• $2 \leq N \leq 200000$
• $1 \leq A_i < B_i \leq N$
• 给定的图保证是一棵树
• 输入均为整数

样例解释 1

如果在顶点 $1$ 上写 $2$，在顶点 $2$ 上写 $1$，则 $dist(1, 2) = 1$，$|E_1 - E_2| = 1$，满足条件 2。其它条件也都满足，因此这种写法可以让 square1001 君感到惊讶。其他如 $(E_1, E_2) = (1, 2)$ 也是正确答案。

样例解释 2

例如 $(E_1, E_2, E_3, E_4) = (2, 3, 4, 1)$ 也是正确答案。

由 ChatGPT 4.1 翻译