题目描述

给定一棵有 $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$ 的主导下标。

样例

4
1 2
2 3
3 4

0
0
0
0

4
1 2
1 3
1 4

1
0
0
0

4
1 2
2 3
2 4

2
1
0
0

数据范围

$1 \le n \le 10^6$

$1 \le x, y \le n$，$x \ne y$