33OJ
登录 注册

#P17553. [JAG 2026 Summer Camp #2] Edge Exchanges

    ID: 20279 远端评测题 2000ms 2048MiB 尝试: 0 已通过: 0 显示难度提高+/省选− 上传者: 标签>Special JudgeICPC2026

[JAG 2026 Summer Camp #2] Edge Exchanges

Problem Description

You are given two trees, AA and BB, each with NN vertices. Both trees have the same labeled vertex set {1,2,…,N}\{1,2,\ldots,N\}.

For each ii (1≤i≤N−11\le i\le N-1), the ii-th edge of AA connects vertices uiu_i and viv_i. For each jj (1≤j≤N−11\le j\le N-1), the jj-th edge of BB connects vertices xjx_j and yjy_j.

For each i=1,2,…,N−1i=1,2,\ldots,N-1, solve the following problem.

Find an integer jj with 1≤j≤N−11\le j\le N-1 such that the following exchange leaves both AA and BB as trees:

  • Remove the edge connecting uiu_i and viv_i from AA, and remove the edge connecting xjx_j and yjy_j from BB.
  • Then, add an edge connecting xjx_j and yjy_j to AA, and add an edge connecting uiu_i and viv_i to BB.

Each exchange is considered independently, starting from the original trees AA and BB.

It can be proved that at least one such integer jj exists for every ii under the given constraints.

Input Format

The input consists of a single test case in the following format.

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 NN is the number of vertices of both AA and BB (2≤N≤2×1052\le N\le 2\times 10^5).

The following N−1N-1 lines describe the edges of AA. For each i=1,…,N−1i=1,\ldots,N-1, the integers uiu_i and viv_i (1≤ui,vi≤N1\le u_i,v_i\le N) mean that the ii-th edge connects vertices uiu_i and viv_i. It is guaranteed that AA is a tree.

The next N−1N-1 lines describe the edges of BB. For each j=1,…,N−1j=1,\ldots,N-1, the integers xjx_j and yjy_j (1≤xj,yj≤N1\le x_j,y_j\le N) mean that the jj-th edge connects vertices xjx_j and yjy_j. It is guaranteed that BB is a tree.

Output Format

Output N−1N-1 lines. For each i=1,2,…,N−1i=1,2,\ldots,N-1, the ii-th line should contain an integer jj satisfying the condition in the problem statement for the ii-th edge of AA.

If there are multiple possible answers, you may output any of them.

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

Hint

In the first line of the sample output, j=1j=1 is chosen for i=1i=1. Exchanging the edge (1,3)(1,3) of AA with the edge (1,2)(1,2) of BB leaves both AA and BB as trees.

For i=2i=2, both the edge of AA and the selected edge of BB are both (2,4)(2,4), so exchanging them does not change either tree. Other valid outputs are also possible.