A12112. Decorate Apple Tree

There is one apple tree in Arkady's garden. It can be represented as a set of junctions connected with branches so that there is only one way to reach any junctions from any other one using branches. The junctions are enumerated from $1$ to $n$ , the junction $1$ is called the root.

A subtree of a junction $v$ is a set of junctions $u$ such that the path from $u$ to the root must pass through $v$ . Note that $v$ itself is included in a subtree of $v$ .

A leaf is such a junction that its subtree contains exactly one junction.

The New Year is coming, so Arkady wants to decorate the tree. He will put a light bulb of some color on each leaf junction and then count the number happy junctions. A happy junction is such a junction $t$ that all light bulbs in the subtree of $t$ have different colors.

Arkady is interested in the following question: for each $k$ from $1$ to $n$ , what is the minimum number of different colors needed to make the number of happy junctions be greater than or equal to $k$ ?

The first line contains a single integer $n$ ( $1 \le n \le 10^5$ ) — the number of junctions in the tree.

The second line contains $n - 1$ integers $p_2$ , $p_3$ , ..., $p_n$ ( $1 \le p_i < i$ ), where $p_i$ means there is a branch between junctions $i$ and $p_i$ . It is guaranteed that this set of branches forms a tree.

Output $n$ integers. The $i$ -th of them should be the minimum number of colors needed to make the number of happy junctions be at least $i$ .

In the first example for $k = 1$ and $k = 2$ we can use only one color: the junctions $2$ and $3$ will be happy. For $k = 3$ you have to put the bulbs of different colors to make all the junctions happy.

In the second example for $k = 4$ you can, for example, put the bulbs of color $1$ in junctions $2$ and $4$ , and a bulb of color $2$ into junction $5$ . The happy junctions are the ones with indices $2$ , $3$ , $4$ and $5$ then.