CF1009F.Dominant Indices

You are given a rooted undirected tree consisting of $n$ vertices. Vertex $1$ is the root.

Let's denote a depth array of vertex $x$ as an infinite sequence $[d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots]$, where $d_{x, i}$ is the number of vertices $y$ such that both conditions hold:

• $x$ is an ancestor of $y$;
• the simple path from $x$ to $y$ traverses exactly $i$ edges.

The dominant index of a depth array of vertex $x$ (or, shortly, the dominant index of vertex $x$) is an index $j$ such that:

• for every $k \lt j$, $d_{x, k} \lt d_{x, j}$;
• for every $k \gt j$, $d_{x, k} \le d_{x, j}$.

For every vertex in the tree calculate its dominant index.

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

我们定义顶点 $x$ 的深度数组为一个无限序列 $[d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots]$，其中 $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}$。

请对树中每个顶点计算其主导索引。

The first line contains one integer $n$ ($1 \le n \le 10^6$) — the number of vertices in a tree.

Then $n - 1$ lines follow, each containing two integers $x$ and $y$ ($1 \le x, y \le n$, $x \ne y$). This line denotes an edge of the tree.

It is guaranteed that these edges form a tree.

第一行包含一个整数 $n$（$1 \le n \le 10^6$）—— 树中顶点的数量。

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

保证这些边构成一棵树。

Output $n$ numbers. $i$-th number should be equal to the dominant index of vertex $i$.

输出 $n$ 个数。其中第 $i$ 个数应等于顶点 $i$ 的主导索引。