Lengthy Traveling Salesman

Karel wants to register his robot for a robot contest. Registering takes a safety certificate for the robot and several forms. Karel starts at the entrance of the organizers' building, visits every office once in a prescribed order, and returns to the entrance. The hallways of the building contain no cycle, so exactly one path runs between any two offices.

Running a contest takes more than a problem statement and a model solution. The organizers also need test data that checks submitted programs, and rejecting inefficient programs takes the visiting order whose walk is as long as possible. Find that order.

The building is a tree with $N$ vertices and one office in every vertex. A tree is a set of vertices joined by edges. Each edge joins two vertices, and exactly one path runs between any two vertices $v_i$ and $v_j$. The length of a path is the number of edges you traverse when you walk from $v_i$ to $v_j$, written $\mathrm{dist}(v_i, v_j)$.

The input holds several test cases. The first line of a test case holds the number of vertices of the tree, $N$ ($2 \le N \le 10\,000$). The vertices are numbered from $0$ to $N-1$. The $i$-th of the next $N-1$ lines holds an integer $f_i$ ($0 \le f_i < i$), meaning that the tree has an edge between vertex $i$ and vertex $f_i$.

One empty line follows each test case. The input ends at the end of the file. There are at most $100$ test cases, and the sum of $N$ over all test cases is at most $50\,000$.

For each test case, print one line with $N$ integers $v_1, \dots, v_N$ separated by spaces. Each of $0, 1, \dots, N-1$ must appear exactly once, and the sum

$\sum_{i=1}^{N-1} \mathrm{dist}(v_i, v_{i+1}) + \mathrm{dist}(v_N, v_1)$

must be as large as possible.

Several permutations usually reach that maximum. Print only the lexicographically smallest one. Comparing two permutations from the front, the one holding the smaller number at the first position where they differ is the lexicographically smaller one.