Nikita 玩一个新的电脑游戏。这个游戏有m个关卡。在每个关卡开始时,游戏中都会出现一个新职业;这个类是 yi 类的子类(并且 yi 被称为这个新类的父类)。因此,类形成一棵树。最初只有一个索引为 1 的类。
将类更改为树中的邻居(子类或父类)需要 1 个硬币。您无法将班级更改回来。将类a更改为类b的成本等于类树中从a到b的路径上类更改的总成本。
假设在第 i 级,将一个类别更改为另一个类别的最大成本为 x。对于每个级别输出类的数量,使得对于每个类都存在一些其他类 y,并且从该类到 y 的距离恰好为 x。
输入
第一行包含一个整数 m — 查询数 (1 ≤ m ≤ 3·105)。
接下来的 m 行包含查询的描述。第 i 行 (1 ≤ i ≤ m) 描述第 i 个级别并包含一个整数 yi - 索引为 i + 1 (1 ≤ yi ≤ i) 的类的父类的索引。
输出
假设在第 i 级,将一个类别更改为另一个类别的最大成本为 x。对于每个级别输出类的数量,使得对于每个类都存在一些其他类 y,并且从该类到 y 的距离恰好为 x。
示例
输入 #1
4 1 1 2 1
输出 #1
2 2 2 3
输入 #2
4 1 1 2 3
输出 #2
2 2 2 2