题目描述

给定一棵有 $n$ 个顶点的有根树，以顶点 $1$ 作为根。

我们定义顶点 $x$ 的深度数组为一个无限序列 $[d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots]$，其中 $d_{x, i}$ 表示满足以下两个条件的顶点 $y$ 的数量：

• $x$ 是 $y$ 的祖先；
• 从 $x$ 到 $y$ 的简单路径恰好经过 $i$ 条边。

顶点 $x$ 的深度数组的主导下标（dominant index）（简称顶点 $x$ 的主导下标）定义为一个下标 $j$，满足：

• 对于所有 $k < j$，都有 $d_{x, k} < d_{x, j}$；
• 对于所有 $k > j$，都有 $d_{x, k} \le d_{x, j}$。

请你计算树中每个顶点的主导下标。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 10^6$），表示树的顶点数。

接下来 $n-1$ 行，每行包含两个整数 $x$ 和 $y$（$1 \le x, y \le n$，$x \ne y$），表示树中的一条边。

保证这些边构成一棵树。

输出格式

输出 $n$ 个数字，第 $i$ 个数字表示顶点 $i$ 的主导下标。

输入输出样例 #1

输入 #1

4
1 2
2 3
3 4

输出 #1

0
0
0
0

输入输出样例 #2

输入 #2

4
1 2
1 3
1 4

输出 #2

1
0
0
0

输入输出样例 #3

输入 #3

4
1 2
2 3
2 4

输出 #3

2
1
0
0

说明/提示

由 ChatGPT 4.1 翻译