Grasshopper Route

A grasshopper is exploring a tree. A tree is an undirected graph in which every two vertices are joined by exactly one path. A grasshopper standing on a vertex can jump to another vertex only if the distance between the two vertices is at most $3$, where the distance is the number of edges on the path that joins them. The grasshopper wants to visit every vertex of the tree exactly once, starting at the vertex $s$ it stands on and finishing at the vertex $t$ it has chosen.

You are given a tree with $n$ vertices and two vertices $s$ and $t$. A grasshopper route for $s$ and $t$ is an ordering $\langle u_1, u_2, \ldots, u_n \rangle$ of all vertices of the tree such that $u_1 = s$, $u_n = t$, and the grasshopper can jump from $u_i$ to $u_{i+1}$ for every $i$ in $\{1, 2, \ldots, n-1\}$. Every pair of vertices of a tree is joined by a grasshopper route, which was proved in 1960.

In the tree drawn below, $\langle 7, 6, 5, 4, 1, 2, 3, 8, 9, 11, 12, 10 \rangle$ is a grasshopper route for $s = 7$ and $t = 10$. The grasshopper can jump from vertex $5$ to vertex $4$ because the distance between them is $3$, but it cannot jump from vertex $5$ to vertex $3$. A tree can have more than one grasshopper route, so the output section fixes one of them.

The figure shows one grasshopper route from $s = 7$ to $t = 10$.

The first line contains an integer $n$, the number of vertices of the tree ($2 \le n \le 100\,000$). Each of the next $n - 1$ lines contains two integers $u$ and $v$ that describe an edge between vertex $u$ and vertex $v$. The vertices are numbered from $1$ to $n$. The last line contains two distinct integers $s$ and $t$, the start vertex and the end vertex of the route.

A tree can have many grasshopper routes, so print the one that the rule below picks. Print the vertices the grasshopper passes through in $n$ lines, one vertex per line, in order.

1. Let $x_1 = s, x_2, \ldots, x_k = t$ be the unique path from $s$ to $t$ in the tree.
2. Delete the $k - 1$ edges of that path. The tree falls apart into $k$ components. Call $C_i$ the component that contains $x_i$, and root $C_i$ at $x_i$.
3. For a vertex $v$ of a rooted tree, define the sequence $f(v)$ as follows. If $v$ has no child, $f(v)$ is the one term sequence $v$. Otherwise let $c_1 < c_2 < \cdots < c_m$ be the children of $v$ in increasing order of vertex number, and let $f(v)$ be $v$, followed by $f(c_1)$ written backwards, then $f(c_2)$ written backwards, and so on up to $f(c_m)$ written backwards.
4. The answer is $f(x_1), f(x_2), \ldots, f(x_{k-1})$ concatenated in this order, followed by $f(x_k)$ written backwards. Each $f(x_i)$ is computed inside the component $C_i$.

This ordering is always a grasshopper route.