给你一棵由 $$$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}$$$。
对于树中的每个顶点计算其主导索引。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 树中的顶点数。
接下来是 $$$n - 1$$$ 行,每行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$)。这条线表示树的边缘。
保证这些边形成一棵树。
输出
输出 $$$n$$$ 个数字。第 $$$i$$$ 个数字应等于顶点 $$$i$$$ 的主导索引。
示例
输入 #1
4 1 2 2 3 3 4
输出 #1
0 0 0 0
输入 #2
4 1 2 1 3 1 4
输出 #2
1 0 0 0
输入 #3
4 1 2 2 3 2 4
输出 #3
2 1 0 0