#P17553. [JAG 2026 Summer Camp #2] Edge Exchanges
[JAG 2026 Summer Camp #2] Edge Exchanges
Problem Description
You are given two trees, and , each with vertices. Both trees have the same labeled vertex set .
For each (), the -th edge of connects vertices and . For each (), the -th edge of connects vertices and .
For each , solve the following problem.
Find an integer with such that the following exchange leaves both and as trees:
- Remove the edge connecting and from , and remove the edge connecting and from .
- Then, add an edge connecting and to , and add an edge connecting and to .
Each exchange is considered independently, starting from the original trees and .
It can be proved that at least one such integer exists for every 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 is the number of vertices of both and ().
The following lines describe the edges of . For each , the integers and () mean that the -th edge connects vertices and . It is guaranteed that is a tree.
The next lines describe the edges of . For each , the integers and () mean that the -th edge connects vertices and . It is guaranteed that is a tree.
Output Format
Output lines. For each , the -th line should contain an integer satisfying the condition in the problem statement for the -th edge of .
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, is chosen for . Exchanging the edge of with the edge of leaves both and as trees.
For , both the edge of and the selected edge of are both , so exchanging them does not change either tree. Other valid outputs are also possible.