AT_abc270_c [ABC270C] Simple path

[problemUrl]: https://atcoder.jp/contests/abc270/tasks/abc270_c $ 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 $ への単純パス上の頂点番号を順に空白区切りで出力せよ。

### 制約 - $ 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 $ をこの順に空白区切りで出力します。 !\[\](https://img.atcoder.jp/abc270/4f4278d90219acdbf32e838353b7a55a.png) ### Sample Explanation 2 木 $ T $ は以下のような形です。 !\[\](https://img.atcoder.jp/abc270/3766cc7963f74e28fa0de6ff660b1998.png)