G - Diverge and Converge 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

Score: 100 points

Problem Statement

You are given a tree A with N vertices. The vertices of A are numbered 1, 2, \dots, N, and the i-th edge (1 \leq i \leq N-1) connects vertices u_i and v_i of A.

Additionally, you are given another tree B with N vertices. The vertices of B are also numbered 1, 2, \dots, N, and the j-th edge (1 \leq j \leq N-1) connects vertices x_j and y_j of B.

Your task is to find a pair of permutations ((P_1, P_2, \dots, P_{N-1}), (Q_1, Q_2, \dots, Q_{N-1})) that satisfies the following conditions:

Conditions

Perform the following operations 1. and 2. in order for k = 1, 2, \dots, N-1. After completing operations 1. and 2. for each k, both A and B must remain as trees.

  1. In tree A, remove the edge connecting vertices u_{P_k} and v_{P_k}, and add an edge connecting vertices x_{Q_k} and y_{Q_k}.
  2. In tree B, remove the edge connecting vertices x_{Q_k} and y_{Q_k}, and add an edge connecting vertices u_{P_k} and v_{P_k}.

It can be proven that under the constraints of this problem, a valid solution always exists.

Constraints

  • All input values are integers.
  • 2 \leq N \leq 1000
  • 1 \leq u_i, v_i, x_j, y_j \leq N
  • The given A and B form trees.

Input

The input is given from Standard Input in the following format:

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}

Output

Output the answer in the following format:

P_1 P_2 \cdots P_{N-1}
Q_1 Q_2 \cdots Q_{N-1}

Sample Input 1

4
1 2
2 3
3 4
1 2
2 4
2 3

Sample Output 1

3 1 2
2 1 3

Before the operation, A is a path graph, and B is a star graph.

After the operation for k = 1, A becomes a star graph, and B becomes a path graph.

In the operations for k = 2, the same edge (in terms of vertex numbers) is removed and added, so the shape of the tree remains unchanged.

After completing the operations for k = 3, the original shapes of trees A and B are completely swapped.

Sample Input 2

2
1 2
2 1

Sample Output 2

1
1

Sample Input 3

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

Sample Output 3

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

配点 : 100 点

問題文

N 頂点の木 A が与えられます。A の頂点には 1,2,\dots ,N の番号がついており、i 番目 (1 ≤ i ≤ N - 1) の辺は A の頂点 u_i,v_i を結んでいます。

さらに、N 頂点の木 B が与えられます。B の頂点にも 1,2,\dots ,N の番号がついており、j 番目 (1 ≤ j ≤ N - 1) の辺は B の頂点 x_j,y_j を結んでいます。

次の条件を満たす (1,2,\dots ,N-1) の順列の組 ((P_1,P_2,\dots,P_{N-1}),(Q_1,Q_2,\dots ,Q_{N-1})) を 1 つ求めてください。

条件

k=1,2,\dots ,N-1 の順に次の 1. と 2. の操作を行う。各 k において 1. と 2. の操作が終わったとき、A も B も再び木となる。

  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} を結ぶ辺を追加する。

なお、この問題の制約下で、答えは必ず存在することが証明できます。

制約

  • 入力はすべて整数
  • 2\le N\le 1000
  • 1\le u_i, v_i, x_j, y_j\le N
  • 与えられる A,B は木をなす

入力

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

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}

入力例 1

4
1 2
2 3
3 4
1 2
2 4
2 3

出力例 1

3 1 2
2 1 3

操作前の木は、 A はパスグラフ、 B はスターグラフになっています。

k=1 の操作が終わったとき、A がスターグラフに、 B がパスグラフになっています。

k=2 の操作では結んでいる頂点の番号が同じ辺を削除・追加しているので、木の形は変わりません。

k=3 の操作が終わったとき、最初の A,B の木の形がちょうど入れ替わっています。

入力例 2

2
1 2
2 1

出力例 2

1
1

入力例 3

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

出力例 3

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