AT_arc117_d [ARC117D] Miracle Tree

有一棵包含 $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$

### 数据范围 - $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 翻译