{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   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."},{"iden":"input","content":"The 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}$"},{"iden":"sample input 1","content":"4\n1 2\n2 3\n3 4\n1 2\n2 4\n2 3"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"2\n1 2\n2 1"},{"iden":"sample output 2","content":"1\n1"},{"iden":"sample input 3","content":"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"},{"iden":"sample output 3","content":"1 2 3 4 5 6\n1 2 6 4 5 3"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}