405109: GYM101798 D Forest (B) - Chicken

Given a forest of n nodes, find an array of n distinct integers such that if we apply the method mentioned in the previous problem, it will generate the given forest.

Please check the previous problem for the details on how the method works.

We care only about the structure of the forest, that is, the labels of the nodes are not important. In other words, the forest generated using the array in your output is considered to match the given forest if it is possible to re-label its nodes such that the set of edges matches the given edges.

Note that trees in the forest are rooted (edges are directed from the parent to the node).

The first line of input contains a single integer n (1 ≤ n ≤ 10⁵), the number of nodes in the forest.

The second line contains n integers p₁, p₂, ..., p_n (0 ≤ p_i < i), where p_i is the parent of node i, or 0 if node i doesn't have a parent.

Print n distinct space-separated integers, each between 1 and n, representing the array that can be used to generate the structure of the given forest.

If there is more than one solution, you can print any of them.

5
0 1 1 3 4

5 2 4 3 1

5
0 1 0 3 4

4 2 1 5 3

Note that in the second example, the generated forest will not be exactly the same as the given one, but it is possible to re-label the nodes so that it matches the given forest. The structure is the same, both forests consist of a chain of length 2 and a chain of length 3.