分数: 100 点
问题陈述
你得到一棵树 A 与 N 顶点。的顶点 A 已编号 1, 2, \dots, N,以及 i第边缘 (1 \leq i \leq N-1) 连接顶点 u_i 和 v_i of A.
此外,你还会获得另一棵树 B 与 N 顶点。的顶点 B 也编号 1, 2, \dots, N,以及 j第边缘 (1 \leq j \leq N-1) 连接顶点 x_j 和 y_j of B.
你的任务是找到一对排列 ((P_1, P_2, \dots, P_{N-1}), (Q_1, Q_2, \dots, Q_{N-1})) 满足以下条件:
条件
执行以下操作 1. 和 2. 以便 k = 1, 2, \dots, N-1. 完成每个操作 1. 和 2. 后 k,两者 A 和 B 必须保留为树。
- 在树中 A,删除连接顶点的边 u_{P_k} 和 v_{P_k},并添加一条连接顶点的边 x_{Q_k} 和 y_{Q_k}.
- 在树中 B,删除连接顶点的边 x_{Q_k} 和 y_{Q_k},并添加一条连接顶点的边 u_{P_k} 和 v_{P_k}.
可以证明,在该问题的约束下,总是存在有效的解。
约束
- 所有输入值均为整数。
- 2 \leq N \leq 1000
- 1 \leq u_i, v_i, x_j, y_j \leq 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