题目描述

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

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

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

顶点 $x$ 的深度数组的显性索引（简称为顶点 $x$ 的显性索引）是一个满足以下条件的索引 $j$：

1. 对于所有 $k < j$，有 $d_{x, k} < d_{x, j}$；
2. 对于所有 $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