P17553 [JAG 2026 Summer Camp #2] Edge Exchanges

You are given two trees, $A$ and $B$, each with $N$ vertices. Both trees have the same labeled vertex set $\{1,2,\ldots,N\}$. For each $i$ ($1\le i\le N-1$), the $i$-th edge of $A$ connects vertices $u_i$ and $v_i$. For each $j$ ($1\le j\le N-1$), the $j$-th edge of $B$ connects vertices $x_j$ and $y_j$. For each $i=1,2,\ldots,N-1$, solve the following problem. Find an integer $j$ with $1\le j\le N-1$ such that the following exchange leaves both $A$ and $B$ as trees: - Remove the edge connecting $u_i$ and $v_i$ from $A$, and remove the edge connecting $x_j$ and $y_j$ from $B$. - Then, add an edge connecting $x_j$ and $y_j$ to $A$, and add an edge connecting $u_i$ and $v_i$ to $B$. Each exchange is considered independently, starting from the original trees $A$ and $B$. It can be proved that at least one such integer $j$ exists for every $i$ under the given constraints.

The input consists of a single test case in the following format. ```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} ``` The integer $N$ is the number of vertices of both $A$ and $B$ ($2\le N\le 2\times 10^5$). The following $N-1$ lines describe the edges of $A$. For each $i=1,\ldots,N-1$, the integers $u_i$ and $v_i$ ($1\le u_i,v_i\le N$) mean that the $i$-th edge connects vertices $u_i$ and $v_i$. It is guaranteed that $A$ is a tree. The next $N-1$ lines describe the edges of $B$. For each $j=1,\ldots,N-1$, the integers $x_j$ and $y_j$ ($1\le x_j,y_j\le N$) mean that the $j$-th edge connects vertices $x_j$ and $y_j$. It is guaranteed that $B$ is a tree.

Output $N-1$ lines. For each $i=1,2,\ldots,N-1$, the $i$-th line should contain an integer $j$ satisfying the condition in the problem statement for the $i$-th edge of $A$. If there are multiple possible answers, you may output any of them.

In the first line of the sample output, $j=1$ is chosen for $i=1$. Exchanging the edge $(1,3)$ of $A$ with the edge $(1,2)$ of $B$ leaves both $A$ and $B$ as trees. For $i=2$, both the edge of $A$ and the selected edge of $B$ are both $(2,4)$, so exchanging them does not change either tree. Other valid outputs are also possible.