问题

高桥王国由 $N$ 个城镇组成，每个城镇都被标号为从 $0$ 到 $N-1$。另外，有 $N-1$ 条连接两个城镇的道路，任意两个城镇之间都可以通过一些道路到达。

作为高桥王国的国王，高桥君正在尝试选择首都。为了作为选择首都的参考，高桥君决定计算"平衡值"。当假设城镇 $v$ 是首都时，"平衡值"是指在不经过城镇 $v$ 的情况下能够相互通行的城镇的集合中最大的大小。

例如，如果假设城镇 $1$ 是首都的情况下，{城镇 $0$，城镇 $4$}、{城镇 $2$}、{城镇 $3$} 等城镇的集合中，可以相互通行且不经过城镇 $1$。其中最大的集合是 {城镇 $0$，城镇 $4$}，其大小为 $2$，因此当假设城镇 $1$ 是首都时，"平衡值"为 $2$。

输入

输入以以下格式从标准输入中获取。

$N$ $p_1$ $p_2$ : $p_{N-1}$

• 第 $1$ 行是一个整数 $N (1 ≦ N ≦ 100,000)$，表示城镇的个数。
• 第 $2$ 行至第 $N-1$ 行，给出了道路的信息。其中第 $i$ 行给出一个整数 $p_i (0 ≦ p_i ≦ i-1)$，表示城镇 $i$ 和城镇 $p_i$ 之间有一条道路。

部分分

此问题可获得部分分。

• 对于满足 $N ≤ 1000$ 的所有测试用例正确答案，可以获得 $30$ 分。

输出

输出为 $N$ 行。其中第 $i$ 行输出假设城镇 $i-1$ 是首都时的"平衡值"，即一个整数。

示例输入1

5
0
1
1
0

示例输出1

3
2
4
4
4

这个案例的输入表示了问题中图示的道路信息。

示例输入2

3
0
0

示例输出2

1
2
2