#P18240. Diverge and Converge
Diverge and Converge
Diverge and Converge
给定一棵有 个顶点的树 ,顶点编号为 。树 的第 条边连接 。
还给定另一棵同样有 个顶点、顶点编号相同的树 。树 的第 条边连接 。
请构造两个 的排列
$$P=(P_1,P_2,\ldots,P_{N-1}),\qquad Q=(Q_1,Q_2,\ldots,Q_{N-1}),$$满足:依次对 执行以下两项操作,在每次完整执行这两项操作后, 和 都仍然是树。
- 在 中删除连接 的边,并添加连接 的边。
- 在 中删除连接 的边,并添加连接 的边。
这里的 始终指输入中的端点, 始终是原来的边编号。两个排列保证每条原边恰好被交换一次。
可以证明,在本题约束下总存在合法答案。输出任意一组即可。
输入格式
第一行一个整数 。
接下来 行,每行两个整数 ,按编号顺序给出 的边。
再接下来 行,每行两个整数 ,按编号顺序给出 的边。
输出格式
输出两行:
- 第一行输出排列 的 个整数。
- 第二行输出排列 的 个整数。
答案不唯一时输出任意合法答案。
数据范围
- 所有输入量均为整数。
- 。
- 。
- 输入的 和 分别构成树。
两棵树允许包含端点相同的边。若某次交换的两条边在几何端点意义下相同,删除后再添加不会改变树形,这也是合法操作。
样例 1
输入
4
1 2
2 3
3 4
1 2
2 4
2 3
输出
3 1 2
2 1 3
说明
初始 是链, 是星形树。
完成第一个步骤后, 变为星形树, 变为链。
第二个步骤交换的是端点相同的边,因此两棵树的形状不变。
完成第三个步骤后,两棵树的边集完全交换。
样例 2
输入
2
1 2
2 1
输出
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
输出
1 2 3 4 5 6
1 2 6 4 5 3