题目描述

给定一个包含 $n$ 个顶点的有根无向树。顶点 $1$ 是根节点。

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

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

顶点 $x$ 的 深度数组的 主下标（或简称为顶点 $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
2 4

2
1
0
0

样例分析

对于顶点 $1$ 来说，$d(1,0)=1,d(1,1)=1,(d1,2)=2$，所以输出 $2$；

对于顶点 $2$ 来说，$d(1,0)=1,d(1,1)=2$，所以输出 $1$；

对于顶点 $3$ 来说，$d(1,0)=1$，所以输出 $0$；

对于顶点 $4$ 来说，$d(1,0)=1$，所以输出 $0$；

数据范围与提示

对于 $100 \%$ 的数据，保证 $1 \le n \le 10^6$。