← 返回题目列表

AtCoder · ttpc2024_1_g

G. 发散与收敛

中文机器翻译题面 查看原题

分数: 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 必须保留为树。

  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 \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