Migrated from Lutece 2752 谈笑风生

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

从前有一棵有着 $n$ 个节点的有根树，其根节点为 $1$ ，树上生活着被称为长者的生物。

长者与长者之间有着密切的联系，对于这种联系，我们定义一个 $d_{x,i}$ 表示对于节点 $x$ ，在其子树中，离它距离正好为 $i$ 的节点数。

现在每个点的长者都对这个 $d_{x,i}$ 十分感兴趣，他们想知道，对于每个节点 $x$ ，其 $d_{x,i}$ 取到最大值时的最小距离 $i'$ 为多少。

注意：在此问题中 $i$ 可以取到 $0$。

Input

第一行输入一个整数 $n$ ，表示树的节点数。

接下来 $n-1$ 行输入两个整数 $a,b$ ，表示树上存在一条连接 $a$ 和 $b$ 的边。

Output

输出共 $n$ 行，每行输出一个数字代表对于每个点，取得答案最大值的时候的最小标号 $i$。

Samples

4
1 2
2 3
2 4

2
1
0
0

Constraints

$1\le n \leq 10^6$

Resources

2022 UESTC ICPC Training for Data Structures