AT_ttpc2024_1_g Diverge and Converge

$ N $ 頂点の木 $ A $ が与えられます。 $ A $ の頂点には $ 1,2,\dots ,N $ の番号がついており、 $ i $ 番目 ( $ 1 > 1. 木 $ A $ において、頂点 $ u_{P_k},v_{P_k} $ を結ぶ辺を削除し、頂点 $ x_{Q_k},y_{Q_k} $ を結ぶ辺を追加する。 > 2. 木 $ B $ において、頂点 $ x_{Q_k},y_{Q_k} $ を結ぶ辺を削除し、頂点 $ u_{P_k},v_{P_k} $ を結ぶ辺を追加する。 なお、この問題の制約下で、答えは必ず存在することが証明できます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ \vdots $ $ x_{N-1} $ $ y_{N-1} $

以下の形式で出力せよ。 > $ P_1 $ $ P_2 $ $ \cdots $ $ P_{N-1} $ $ Q_1 $ $ Q_2 $ $ \cdots $ $ Q_{N-1} $

### Sample Explanation 1 操作前の木は、 $ A $ はパスグラフ、 $ B $ はスターグラフになっています。 $ k=1 $ の操作が終わったとき、 $ A $ がスターグラフに、 $ B $ がパスグラフになっています。 $ k=2 $ の操作では結んでいる頂点の番号が同じ辺を削除・追加しているので、木の形は変わりません。 $ k=3 $ の操作が終わったとき、最初の $ A,B $ の木の形がちょうど入れ替わっています。 ### Constraints - 入力はすべて整数 - $ 2\le N\le 1000 $ - $ 1\le u_i, v_i, x_j, y_j\le N $ - 与えられる $ A,B $ は木をなす