Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Decorate Apple Tree

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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$$$?

Input

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

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$$$.

Examples

Input

3 1 1

Output

1 1 2

Input

5 1 1 3 3

Output

1 1 1 2 3

Note

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/18/2018 23:24:14 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|