子树和（子树大小）

题目概述

给定一棵共有 n 个结点的有根树，根结点为 1。 每个结点的权值都视为 1。 你的任务是：对每个结点 i，求它的子树和——也就是以 i 为根的整棵子树中结点的数量。

注：因为每个结点权值都是 1，子树和 = 子树结点数。

输入格式

• 第一行：一个整数 n（结点数）。
• 接下来 n-1 行：第 i 行给出一个整数 \(f_{i+1}\)，表示结点 i+1 的父亲是 \(f_{i+1}\)。保证 \(f_{i+1} < i+1\)，即父亲编号总是比子结点小。

这等价于：你依次读入 2、3、…、n 号结点的父亲编号。

输出格式

输出 n 行。 第 i 行输出一个整数，表示结点 i 的子树中有多少个结点（包含 i 自身）。

样例

输入

5
1
2
3
3

输出

5
4
3
1
1

解释 边为：1-2, 2-3, 3-4, 3-5。

• 以 1 为根的整棵树共有 5 个结点
• 2 的子树共有 4 个结点（{2,3,4,5}）
• 3 的子树共有 3 个结点（{3,4,5}）
• 4 的子树共有 1 个结点（{4}）
• 5 的子树共有 1 个结点（{5}）

数据范围

• \(1 \le n \le 1000\)