AT_ttpc2024_1_g Diverge and Converge
题目描述
给定一棵有 $N$ 个顶点的树 $A$。顶点的编号从 $1$ 到 $N$，其中第 $i$ 条边（$1 \le i \le N-1$）连接了顶点 $u_i$ 和 $v_i$。
同时，你还得到了一棵同样有 $N$ 个顶点的树 $B$。树 $B$ 的顶点编号也是从 $1$ 到 $N$，其中第 $j$ 条边（$1 \le j \le N-1$）连接了顶点 $x_j$ 和 $y_j$。
你的任务是找到一个排列对 $((P_1, P_2, \dots, P_{N-1}), (Q_1, Q_2, \dots, Q_{N-1}))$，使得以下条件成立：
对于每个 $k=1, 2, \dots, N-1$，依次执行以下两步操作。在每个 $k$ 的两步操作执行完毕后，$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}$ 的边。
请注意，根据题目的限制条件，可以保证一定存在这样的排列对。
输入格式
输入从标准输入读取，格式如下：
```
N
u_1 v_1
u_2 v_2
...
u_{N-1} v_{N-1}
x_1 y_1
x_2 y_2
...
x_{N-1} y_{N-1}
```
输出格式
输出排列的结果，格式如下：
```
P_1 P_2 ... P_{N-1}
Q_1 Q_2 ... Q_{N-1}
```
说明/提示
- $2 \le N \le 1000$
- $1 \le u_i, v_i, x_j, y_j \le N$
- 给定的 $A$ 和 $B$ 保证是树
### 样例解释 1
在操作开始时，树 $A$ 是一条直线型的路径树，而树 $B$ 是星型树。当 $k=1$ 操作完成后，$A$ 变成星型树，而 $B$ 变成路径树。在 $k=2$ 操作中，删除和添加的边具有相同的顶点，因此树的形状并没有改变。到 $k=3$ 操作结束时，$A$ 和 $B$ 的结构已经成功互换。
**本翻译由 AI 自动生成**