메뚜기 경로

메뚜기 한 마리가 트리를 탐험하려고 한다. 트리는 어떤 두 정점도 정확히 하나의 경로로 이어진 무향 그래프다. 트리의 한 정점에 있는 메뚜기는 거리가 $3$ 이하인 다른 정점으로만 뛸 수 있다. 두 정점의 거리는 두 정점을 잇는 경로에 있는 간선의 수다. 메뚜기는 지금 있는 정점 $s$에서 출발해 원하는 정점 $t$에서 끝나도록, 트리의 모든 정점을 정확히 한 번씩 방문하려고 한다.

정점이 $n$개인 트리와 두 정점 $s$, $t$가 주어진다. $s$와 $t$의 메뚜기 경로는 트리의 모든 정점을 나열한 순서 $\langle u_1, u_2, \ldots, u_n \rangle$ 중에서 $u_1 = s$, $u_n = t$이고 $\{1, 2, \ldots, n-1\}$의 모든 $i$에 대해 메뚜기가 $u_i$에서 $u_{i+1}$로 뛸 수 있는 것을 말한다. 트리의 어떤 두 정점을 골라도 메뚜기 경로가 존재한다는 사실은 1960년에 증명되었다.

아래 그림의 트리에서 $s = 7$, $t = 10$일 때 $\langle 7, 6, 5, 4, 1, 2, 3, 8, 9, 11, 12, 10 \rangle$은 메뚜기 경로다. 정점 $5$와 정점 $4$의 거리는 $3$이므로 메뚜기는 $5$에서 $4$로 뛸 수 있지만, $5$에서 $3$으로는 뛰지 못한다. 메뚜기 경로는 여러 개일 수 있으므로 출력에서 그중 하나를 정해 둔다.

그림: $s = 7$에서 $t = 10$으로 가는 메뚜기 경로 하나.

첫 줄에 트리의 정점 수 $n$이 주어진다 ($2 \le n \le 100\,000$). 다음 $n - 1$개의 줄에는 각각 두 정수 $u$와 $v$가 주어지며, 정점 $u$와 정점 $v$를 잇는 간선을 뜻한다. 정점에는 $1$부터 $n$까지 번호가 붙어 있다. 마지막 줄에는 서로 다른 두 정수 $s$와 $t$가 주어진다. 각각 메뚜기 경로의 시작 정점과 끝 정점이다.

메뚜기 경로는 여러 개일 수 있으므로, 다음 규칙이 정하는 경로 하나를 출력한다. 메뚜기가 지나는 정점을 순서대로 $n$개의 줄에 한 정점씩 출력한다.

1. $s$에서 $t$로 가는 유일한 경로를 $x_1 = s, x_2, \ldots, x_k = t$라고 하자.
2. 이 경로의 간선 $k - 1$개를 트리에서 지우면 트리가 $k$개의 컴포넌트로 나뉜다. $x_i$가 들어 있는 컴포넌트를 $C_i$라 하고, $C_i$는 $x_i$를 루트로 삼는다.
3. 루트가 정해진 트리의 정점 $v$에 대해 수열 $f(v)$를 다음과 같이 정의한다. $v$에 자식이 없으면 $f(v)$는 정점 $v$ 하나짜리 수열이다. 자식이 있으면 번호가 작은 것부터 $c_1 < c_2 < \cdots < c_m$이라 할 때, $f(v)$는 $v$ 뒤에 $f(c_1)$을 뒤집은 수열, $f(c_2)$를 뒤집은 수열, 그렇게 $f(c_m)$을 뒤집은 수열까지 차례로 이어 붙인 수열이다.
4. 답은 $f(x_1), f(x_2), \ldots, f(x_{k-1})$을 이 순서로 이어 붙인 뒤 $f(x_k)$를 뒤집은 수열을 마지막에 붙인 것이다. 각 $f(x_i)$는 컴포넌트 $C_i$ 안에서 계산한다.

이 순서는 항상 메뚜기 경로다.