회사 배치

엘리는 큰 소프트웨어 회사에서 일하기 시작했다. 회사의 위계는 트리 구조이며, 사장을 제외한 모든 사람은 직속 상사가 정확히 한 명이다. 회사는 팀으로 나뉘는데, 한 프로그래머와 그 사람의 직속 및 간접 부하 직원 전체를 하나의 팀으로 본다. 따라서 한 팀은 여러 개의 작은 팀으로 이루어질 수 있다. 예를 들어 마이크로소프트에는 Office를 담당하는 팀이 있고, 이 팀은 Word, Excel 등을 담당하는 팀으로 구성된다. 엘리의 경우 스탄초는 페쇼와 엘리의 상사이고, 엘리는 크리스의 상사이며, 페쇼는 고쇼와 토쇼의 상사이다. 그러면 스탄초, 페쇼, 엘리, 크리스, 고쇼, 토쇼가 하나의 팀을 이룬다. 엘리와 크리스는 한 팀이고, 페쇼, 토쇼, 고쇼는 다른 팀이다.

사무실은 매우 길고 좁아서 컴퓨터를 한 줄로만 놓을 수 있다. 사장은 가장 왼쪽 컴퓨터를 차지했고, 프로그래머를 다음 조건을 만족하도록 배치하려고 한다. (1) 모든 프로그래머의 직속 상사는 그 프로그래머보다 왼쪽에 앉아 있어야 한다. (2) 각 팀의 구성원은 연속된 컴퓨터를 차지해야 하며, 서로 옆에 앉아야 한다. 위 예시에서 가능한 배치 중 하나는 스탄초, 페쇼, 고쇼, 토쇼, 엘리, 크리스이다.

회사 구조가 주어졌을 때 프로그래머의 배치 순서를 출력하는 프로그램을 작성하라. 가능한 배치가 여러 개면 사전순으로 가장 앞서는 배치를 출력한다. 배치 A가 B보다 사전순으로 앞선다는 것은 처음으로 달라지는 위치에서 A의 번호가 B의 번호보다 작다는 뜻이다. 예를 들어 {1, 3, 4, 6, 7, 2, 5}는 {1, 3, 5, 2, 4, 6, 7}보다 앞선다.

첫 줄에 프로그래머의 수 $N$이 주어진다. 프로그래머는 1부터 $N$까지 번호가 붙어 있으며, 1번은 직속 상사가 없는 사장이다. 이어지는 $N - 1$개의 줄에는 두 정수 $W_1$, $W_2$가 주어지며, 이는 $W_1$이 $W_2$의 직속 상사임을 뜻한다.

$1 \le N \le 200{,}000$

첫 번째 예시에서 스탄초는 1번, 엘리는 2번, 크리스는 5번, 페쇼는 4번, 고쇼는 3번, 토쇼는 6번이다.