{"raw_statement":[{"iden":"statement","content":"You are given two trees with the same number of leaves L, your task is to merge the two trees' leaves in a way that ensures the following:\n\nNote that by merging two leaves a and b, the resulting node will have both edges of a and b.\n\nThe first line of input contains one integer N (3 ≤ N ≤ 105), the number of nodes in the first tree.\n\nThen follows N - 1 lines, the ith line contains two integers u and v (1 ≤ u, v ≤ N), the indices of the nodes connected by the ith edge in the first tree.\n\nThe next line contains an integer M (3 ≤ M ≤ 105), the number of nodes in the second tree.\n\nThen follows M - 1 lines, the ith line contains two integers u and v (1 ≤ u, v ≤ M), the indices of the nodes connected by the ith edge in the second tree.\n\nIt is guaranteed that the two trees will have the same number of leaves L.\n\nOn a single line print the number of colors needed to color the resulting graph.\n\nFollowed by L lines, the ith line of them contains two integers u and v (1 ≤ u ≤ N)(1 ≤ v ≤ M), the indices of the leaves to be merged, where u is a leaf in the first tree, and v is a leaf in the second tree.\n\nIf there’s more than one possible solution, print any of them.\n\nIn the first sample, the two trees can be illustrated as follows:\n\nAfter merging node 2 from first tree with node 1 from the second tree, and node 3 from the first tree with node 2 from the second tree, the resulting graph is illustrated in the figure below:\n\nThe minimum number of colors required to satisfy the problem constraints is 2.\n\n"},{"iden":"input","content":"The first line of input contains one integer N (3 ≤ N ≤ 105), the number of nodes in the first tree.Then follows N - 1 lines, the ith line contains two integers u and v (1 ≤ u, v ≤ N), the indices of the nodes connected by the ith edge in the first tree.The next line contains an integer M (3 ≤ M ≤ 105), the number of nodes in the second tree.Then follows M - 1 lines, the ith line contains two integers u and v (1 ≤ u, v ≤ M), the indices of the nodes connected by the ith edge in the second tree.It is guaranteed that the two trees will have the same number of leaves L."},{"iden":"output","content":"On a single line print the number of colors needed to color the resulting graph.Followed by L lines, the ith line of them contains two integers u and v (1 ≤ u ≤ N)(1 ≤ v ≤ M), the indices of the leaves to be merged, where u is a leaf in the first tree, and v is a leaf in the second tree.If there’s more than one possible solution, print any of them."},{"iden":"examples","content":"Input31 21 333 12 3Output22 13 2Input41 22 33 433 11 2Output34 21 3"},{"iden":"note","content":"  A tree of N nodes is a connected undirected graph with N - 1 edges.  A node is a leaf if and only if it is connected to at most one other node. In the first sample, the two trees can be illustrated as follows:  After merging node 2 from first tree with node 1 from the second tree, and node 3 from the first tree with node 2 from the second tree, the resulting graph is illustrated in the figure below:  The minimum number of colors required to satisfy the problem constraints is 2."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T_1 = (V_1, E_1) $ and $ T_2 = (V_2, E_2) $ be two trees with $ |V_1| = N $, $ |V_2| = M $, and the same number of leaves $ L $.  \nLet $ L_1 \\subseteq V_1 $, $ L_2 \\subseteq V_2 $ denote the sets of leaves of $ T_1 $ and $ T_2 $, respectively, with $ |L_1| = |L_2| = L $.  \n\n**Constraints**  \n1. $ 3 \\leq N, M \\leq 10^5 $  \n2. $ T_1 $ and $ T_2 $ are trees (connected, acyclic, undirected).  \n3. The merging operation identifies each leaf $ u \\in L_1 $ with exactly one leaf $ v \\in L_2 $, forming a bijection $ f: L_1 \\to L_2 $.  \n4. The resulting graph $ G = (V, E) $ is formed by:  \n   - $ V = (V_1 \\cup V_2) / \\sim $, where $ u \\sim f(u) $ for all $ u \\in L_1 $,  \n   - $ E = E_1 \\cup E_2 $.  \n\n**Objective**  \n1. Compute the **minimum number of colors** required for a proper vertex coloring of $ G $.  \n2. Output a bijection $ f: L_1 \\to L_2 $ specifying which leaves to merge.  \n\n**Note**: The chromatic number of $ G $ depends on the structure of the merged graph; the goal is to minimize it over all possible bijections $ f $.","simple_statement":"You are given two trees with the same number of leaves. Merge each leaf from the first tree with exactly one leaf from the second tree. After merging, color all edges of the resulting graph so that no two adjacent edges have the same color. Find the minimum number of colors needed, and output one valid way to pair the leaves.","has_page_source":false}