← 返回题目列表

Codeforces · 768/G

G. 冬日的风

中文机器翻译题面 查看原题

给定一棵有 n 个节点的有根树。夜王从树中删除了一个节点以及与其相关的所有边。这样做会分裂树并形成森林。被删除的节点不是森林的一部分。

森林中树的根是该树中没有父节点的节点。我们将森林的强度定义为森林中最大树木的大小。

琼恩·雪诺想要最小化森林的力量。为此,他最多可以执行一次以下操作。

他删除节点与其父节点之间的边,并在该节点与森林中的任何其他节点之间插入一条新边,以使森林中的树总数保持不变。

对于每个节点 v,您需要找到删除节点 v 时形成的森林强度的最小值。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 105) — 树中的顶点数。接下来的 n 行中的每一行都包含一对顶点索引 ui 和 vi (1 ≤ ui, vi ≤ n),其中 ui 是 vi 的父级。如果 ui = 0 则 vi 是根。

输出

打印 n 行,每行包含一个整数。其中第i个应该等于移除第i个节点且琼恩·雪诺最多执行一次上述操作时形成的森林强度的最小值。

示例

输入 #1

10
0 1
1 2
1 3
1 4
2 5
2 6
3 7
4 8
4 9
5 10

输出 #1

3
4
5
5
5
9
9
9
9
9

输入 #2

2
2 1
0 2

输出 #2

1
1

注意

第一个测试用例的树如下所示。 当您删除第一个节点时,树会分裂形成以下森林。该森林的强度为 4。琼恩·雪诺现在将顶点 10 的父级从 5 更改为 3。森林的强度现在变为 3。