配点 : $300$ 点

問題文

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

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

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

制約

• $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$
• 入力はすべて整数
• 与えられるグラフは木

入力

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

$N$ $X$ $Y$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_{N-1}$ $V_{N-1}$

出力

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

5 2 5
1 2
1 3
3 4
3 5

2 1 3 5

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

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

1 2

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