题目描述

$N$ 頂点の木 $T$ があり、 $i$ $(1\leq\ i\leq\ N-1)$ 番目の辺は頂点 $U_i$ と頂点 $V_i$ を結んでいます。

$T$ 上の相異なる $2$ 頂点 $X,Y$ が与えられるので、 頂点 $X$ から頂点 $Y$ への単純パス上の頂点（端点含む）を順に列挙してください。

ただし、木上の任意の相異なる $2$ 頂点 $a,b$ について、$a$ から $b$ への単純パスがただ一つ存在することが証明できます。

単純パスとは？グラフ $G$ 上の頂点 $X,Y$ に対して、頂点列 $v_1,v_2,\ \ldots,\ v_k$ であって、 $v_1=X$, $v_k=Y$ かつ、$1\leq\ i\leq\ k-1$ に対して $v_i$ と $v_{i+1}$ が辺で結ばれているようなものを頂点 $X$ から頂点 $Y$ への パス と呼びます。 さらに、$v_1,v_2,\ \ldots,\ v_k$ がすべて異なるようなものを頂点 $X$ から頂点 $Y$ への 単純パス と呼びます。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $X$ $Y$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_{N-1}$ $V_{N-1}$

输出格式

頂点 $X$ から頂点 $Y$ への単純パス上の頂点番号を順に空白区切りで出力せよ。

题目大意

给定一个树，求这个树上两个点的简单路径。请按照 $x,a,b,c,\cdots,y$ 的顺序输出。（输入的两个点的顺序是 $x$，$y$）

5 2 5
1 2
1 3
3 4
3 5

2 1 3 5

6 1 2
3 1
2 5
1 2
4 1
2 6

1 2

提示

制約

• $1\leq\ N\leq\ 2\times\ 10^5$
• $1\leq\ X,Y\leq\ N$
• $X\neq\ Y$
• $1\leq\ U_i,V_i\leq\ N$
• 入力はすべて整数
• 与えられるグラフは木

Sample Explanation 1

木 $T$ は以下のような形であり、頂点 $2$ から頂点 $5$への単純パスは 頂点 $2$ $\to$ 頂点 $1$ $\to$ 頂点 $3$ $\to$ 頂点 $5$ となります。 よって、$2,1,3,5$ をこの順に空白区切りで出力します。 

Sample Explanation 2

木 $T$ は以下のような形です。