Description

​ A 国一年一度的盛会——国际健美操大赛就要开始了。

​ A 国共有 $n$ 座城市, 构成一棵以 1 号城市为根的有根树, 除了 1 号城市以外, 每个城市都有唯一的 一个依附城市. 健美操大会将在 A 国 $n$ 个城市中的某一个举行, 定义在城市 $x$ 举行盛会的交通不便程度为将城市 $x$ 删去后最大联通块的大小。

​ 为了提高交通运输能力, A 国政府可以进行一次如下操作: 在删去 $x$ 号城市后, 可以更改某个城市 的依附城市 (不能对 1 号城市和依附城市为 $x$ 的城市进行该操作)。 现在 A 国的国王想要知道对于每个 城市而言, 在这个城市举行盛会的交通不便程度最小可能是多少?

Input Format

​ 第一行一个整数 $n$

​ 接下来一行 $n − 1$ 个正整数, 第 $i$ 个数表示 $i + 1$ 号城市的依附城市。

Output Format

​ $n$ 行, 每行一个整数, 第 $i$ 行表示在 $i$ 号城市举行盛会的最小不便程度。

Sample Input

12
1 1 1 4 1 1 5 2 8 1 6 

Sample Output

3
6
11
6
7
6
11
8
11
11
11
11

Constraints

​ 对于 100% 的数据: $n ≤ 10^5$.

​ Subtask1(19pts): $n \le 2000$

​ Subtask2(22pts): $i$号城市的依附城市在[1,$i-1$]中均匀随机

​ Subtask3(27pts): $n \le 50000$

​ Subtask4(32pts): 无特殊限制

Download

样例数据