{"problem":{"name":"Diverge and Converge","description":{"content":"You are given a tree $A$ with $N$ vertices. The vertices of $A$ are numbered $1, 2, \\dots, N$, and the $i$\\-th edge ($1 \\leq i \\leq N-1$) connects vertices $u_i$ and $v_i$ of $A$. Additionally, you ar","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"ttpc2024_1_g"},"statements":[{"statement_type":"Markdown","content":"You are given a tree $A$ with $N$ vertices. The vertices of $A$ are numbered $1, 2, \\dots, N$, and the $i$\\-th edge ($1 \\leq i \\leq N-1$) connects vertices $u_i$ and $v_i$ of $A$.\nAdditionally, you are given another tree $B$ with $N$ vertices. The vertices of $B$ are also numbered $1, 2, \\dots, N$, and the $j$\\-th edge ($1 \\leq j \\leq N-1$) connects vertices $x_j$ and $y_j$ of $B$.\nYour task is to find a pair of permutations $((P_1, P_2, \\dots, P_{N-1}), (Q_1, Q_2, \\dots, Q_{N-1}))$ that satisfies the following conditions:\n\n> **Conditions**\n> Perform the following operations 1. and 2. in order for $k = 1, 2, \\dots, N-1$. **After completing operations 1. and 2. for each $k$**, both $A$ and $B$ must remain as trees.\n> \n> 1.  In tree $A$, remove the edge connecting vertices $u_{P_k}$ and $v_{P_k}$, and add an edge connecting vertices $x_{Q_k}$ and $y_{Q_k}$.\n> 2.  In tree $B$, remove the edge connecting vertices $x_{Q_k}$ and $y_{Q_k}$, and add an edge connecting vertices $u_{P_k}$ and $v_{P_k}$.\n\nIt can be proven that under the constraints of this problem, a valid solution always exists.\n\n## Constraints\n\n*   All input values are integers.\n*   $2 \\leq N \\leq 1000$\n*   $1 \\leq u_i, v_i, x_j, y_j \\leq N$\n*   The given $A$ and $B$ form trees.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_{N-1}$ $v_{N-1}$\n$x_1$ $y_1$\n$x_2$ $y_2$\n$\\vdots$\n$x_{N-1}$ $y_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"ttpc2024_1_g","tags":[],"sample_group":[["4\n1 2\n2 3\n3 4\n1 2\n2 4\n2 3","3 1 2\n2 1 3\n\nBefore the operation, $A$ is a path graph, and $B$ is a star graph.\nAfter the operation for $k = 1$, $A$ becomes a star graph, and $B$ becomes a path graph.\nIn the operations for $k = 2$, the same edge (in terms of vertex numbers) is removed and added, so the shape of the tree remains unchanged.\nAfter completing the operations for $k = 3$, the original shapes of trees $A$ and $B$ are completely swapped."],["2\n1 2\n2 1","1\n1"],["7\n1 2\n1 3\n2 4\n2 5\n3 6\n3 7\n1 5\n1 6\n1 7\n5 2\n6 3\n7 4","1 2 3 4 5 6\n1 2 6 4 5 3"]],"created_at":"2026-03-03 11:01:14"}}