#P18240. Diverge and Converge

Diverge and Converge

Diverge and Converge

给定一棵有 NN 个顶点的树 AA,顶点编号为 1,2,…,N1,2,\ldots,N。树 AA 的第 ii 条边连接 ui,viu_i,v_i。

还给定另一棵同样有 NN 个顶点、顶点编号相同的树 BB。树 BB 的第 jj 条边连接 xj,yjx_j,y_j。

请构造两个 1,2,…,N−11,2,\ldots,N-1 的排列

$$P=(P_1,P_2,\ldots,P_{N-1}),\qquad Q=(Q_1,Q_2,\ldots,Q_{N-1}),$$

满足:依次对 k=1,2,…,N−1k=1,2,\ldots,N-1 执行以下两项操作,在每次完整执行这两项操作后,AA 和 BB 都仍然是树。

  1. 在 AA 中删除连接 uPk,vPku_{P_k},v_{P_k} 的边,并添加连接 xQk,yQkx_{Q_k},y_{Q_k} 的边。
  2. 在 BB 中删除连接 xQk,yQkx_{Q_k},y_{Q_k} 的边,并添加连接 uPk,vPku_{P_k},v_{P_k} 的边。

这里的 ui,vi,xj,yju_i,v_i,x_j,y_j 始终指输入中的端点,Pk,QkP_k,Q_k 始终是原来的边编号。两个排列保证每条原边恰好被交换一次。

可以证明,在本题约束下总存在合法答案。输出任意一组即可。

输入格式

第一行一个整数 NN。

接下来 N−1N-1 行,每行两个整数 ui,viu_i,v_i,按编号顺序给出 AA 的边。

再接下来 N−1N-1 行,每行两个整数 xj,yjx_j,y_j,按编号顺序给出 BB 的边。

输出格式

输出两行:

  • 第一行输出排列 PP 的 N−1N-1 个整数。
  • 第二行输出排列 QQ 的 N−1N-1 个整数。

答案不唯一时输出任意合法答案。

数据范围

  • 所有输入量均为整数。
  • 2≤N≤10002\le N\le1000。
  • 1≤ui,vi,xj,yj≤N1\le u_i,v_i,x_j,y_j\le N。
  • 输入的 AA 和 BB 分别构成树。

两棵树允许包含端点相同的边。若某次交换的两条边在几何端点意义下相同,删除后再添加不会改变树形,这也是合法操作。

样例 1

输入

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

输出

3 1 2
2 1 3

说明

初始 AA 是链,BB 是星形树。

完成第一个步骤后,AA 变为星形树,BB 变为链。

第二个步骤交换的是端点相同的边,因此两棵树的形状不变。

完成第三个步骤后,两棵树的边集完全交换。

样例 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