给定一棵有 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。