P17553 [JAG 2026 Summer Camp #2] Edge Exchanges

给定两棵树 $A$ 和 $B$，每棵树都有 $N$ 个顶点。两棵树具有相同的带标号顶点集 $\{1,2,\ldots,N\}$。 对于每个 $i$（$1\le i\le N-1$），$A$ 的第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。对于每个 $j$（$1\le j\le N-1$），$B$ 的第 $j$ 条边连接顶点 $x_j$ 和 $y_j$。 对于每个 $i=1,2,\ldots,N-1$，解决以下问题。 找到一个满足 $1\le j\le N-1$ 的整数 $j$，使得进行下述交换后，$A$ 和 $B$ 仍然都是树： - 从 $A$ 中删除连接 $u_i$ 和 $v_i$ 的边，从 $B$ 中删除连接 $x_j$ 和 $y_j$ 的边。 - 然后在 $A$ 中添加连接 $x_j$ 和 $y_j$ 的边，在 $B$ 中添加连接 $u_i$ 和 $v_i$ 的边。 每次交换独立考虑，均从原始的树 $A$ 和 $B$ 开始。 可以证明，在给定约束下，对于每个 $i$，都至少存在一个满足要求的整数 $j$。

输入仅包含一组测试数据，格式如下。 ```text 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} ``` 整数 $N$ 是 $A$ 和 $B$ 的顶点数（$2\le N\le 2\times 10^5$）。 接下来的 $N-1$ 行描述 $A$ 的边。对于每个 $i=1,\ldots,N-1$，整数 $u_i,v_i$（$1\le u_i,v_i\le N$）表示第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。保证 $A$ 是一棵树。 再接下来的 $N-1$ 行描述 $B$ 的边。对于每个 $j=1,\ldots,N-1$，整数 $x_j,y_j$（$1\le x_j,y_j\le N$）表示第 $j$ 条边连接顶点 $x_j$ 和 $y_j$。保证 $B$ 是一棵树。

输出 $N-1$ 行。对于每个 $i=1,2,\ldots,N-1$，第 $i$ 行应包含一个整数 $j$，使其对于 $A$ 的第 $i$ 条边满足题目描述中的条件。 如果有多个合法答案，可以输出任意一个。

样例输出的第一行对 $i=1$ 选择了 $j=1$。将 $A$ 的边 $(1,3)$ 与 $B$ 的边 $(1,2)$ 交换后，$A$ 和 $B$ 仍然都是树。 对于 $i=2$，$A$ 的边和所选的 $B$ 的边都是 $(2,4)$，因此交换它们不会改变任意一棵树。也可能存在其他合法输出。