有一棵以顶点 $1$ 为根的树，共有 $N$ 个顶点。小婷老师会在每一个叶子顶点安装一盏带有颜色的灯。

如果某个顶点的子树中，所有叶子上的灯颜色两两不同，就称这个顶点是“快乐”的。相同的颜色可以用在不同叶子上，但这样可能使同时包含这些叶子的某些祖先顶点不快乐。

对于每个 $k=1,2,\ldots,N$，请分别计算：为了让树中至少有 $k$ 个快乐顶点，最少需要使用多少种不同的颜色。

输入格式

第一行输入一个整数 $N$，表示顶点数量。

第二行输入 $N-1$ 个整数 $p_2,p_3,\ldots,p_N$，其中 $p_i$ 表示顶点 $i$ 的父亲。

输出格式

在一行中输出 $N$ 个整数。第 $k$ 个整数表示让至少 $k$ 个顶点快乐所需的最少颜色种类数。

1

1

3
1 2

1 1 1

3
1 1

1 1 2

数据范围与约定

• $1\le N\le10^5$
• $1\le p_i<i$