가장 긴 외판원 순회

카렐은 로봇 대회에 자신의 로봇을 등록하려고 한다. 등록하려면 로봇의 안전 인증서를 받고 여러 서류를 작성해야 한다. 그래서 대회 주최 측 건물 입구에서 출발해 정해진 순서대로 사무실을 모두 한 번씩 들른 다음 다시 입구로 돌아와야 한다. 다행히 건물 복도는 사이클을 이루지 않아서, 두 사무실 사이의 경로는 언제나 하나뿐이다.

대회를 열려면 문제 지문과 정답 코드만으로는 부족하다. 제출된 코드를 검증할 테스트 데이터도 만들어야 한다. 특히 비효율적인 풀이를 걸러내려면 걷는 거리가 가장 긴 방문 순서가 필요하다. 그 순서를 찾아라.

건물은 정점이 $N$개인 트리이고, 각 정점에 사무실이 하나씩 있다. 트리는 간선으로 이어진 정점의 모임이다. 간선 하나는 정점 두 개를 잇고, 임의의 두 정점 $v_i$와 $v_j$ 사이에는 경로가 정확히 하나 있다. 경로의 길이는 $v_i$에서 $v_j$로 갈 때 지나는 간선의 수이고, 이를 $\mathrm{dist}(v_i, v_j)$로 쓴다.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 트리의 정점 수 $N$ ($2 \le N \le 10\,000$)이 주어진다. 정점 번호는 $0$부터 $N-1$까지다. 이어지는 $N-1$개 줄 가운데 $i$번째 줄에는 정수 $f_i$ ($0 \le f_i < i$)가 주어진다. 이는 정점 $i$와 정점 $f_i$를 잇는 간선이 트리에 있다는 뜻이다.

각 테스트 케이스 뒤에는 빈 줄이 하나 온다. 입력은 파일이 끝나면 함께 끝난다. 테스트 케이스는 $100$개 이하이고, 모든 테스트 케이스의 $N$을 더한 값은 $50\,000$ 이하다.

각 테스트 케이스마다 한 줄에 정수 $N$개 $v_1, \dots, v_N$을 공백으로 구분해 출력한다. $0, 1, \dots, N-1$이 각각 정확히 한 번씩 나와야 하고, 합

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

이 가능한 최댓값이어야 한다.

합을 최대로 만드는 순열은 보통 여러 개다. 그중 사전순으로 가장 앞서는 순열 하나만 출력한다. 두 순열을 앞에서부터 비교해 값이 처음으로 달라지는 자리에서 더 작은 수가 놓인 쪽이 사전순으로 앞선다.