Problem C
Deep Tree Generation
When preparing problems for programming contests, it is important to know how to generate rooted trees. Here is probably the easiest way to do that:
-
Generate a list of $N-1$ integers $p_2, p_3, \dots , p_N$, where $1 \leq p_i < i$.
-
Let $p_i$ be the parent of vertex $i$ in the tree. You now have a tree rooted at vertex $1$.
This algorithm is great, but it tends to produce very shallow trees, at least if the numbers $p_i$ are generated uniformly at random.
You are given a list of numbers $p_2, p_3, \dots , p_N$ that define a rooted tree, and your task is to rearrange the numbers so that the resulting tree is as deep as possible. The depth of a rooted tree is defined as the maximum distance from the root (vertex $1$) to any other vertex.
Input
The first line of input contains the integer $N$ ($2 \leq N \leq 10^5$).
The second line of input contains the $N-1$ integers $p_2, p_3, \dots , p_N$ ($1 \leq p_i < i$). So for example, the first number must be $1$, the second can be $1$ or $2$, and so on.
Output
Print one line with $N-1$ integers $q_2, q_3, \dots q_N$, which is a rearrangement of the numbers in the input, such that the resulting tree is as deep as possible. These numbers must define a valid rooted tree, so $1 \leq q_i < i$ must be satisfied. If there are many solutions, you can print any of them.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 1 2 1 4 4 |
1 1 2 4 4 |
