{"problem":{"name":"B. 2Trees","description":{"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: Note that by merging two leaves a and b, the resulting node ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10125B"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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.\n\n## Output\n\nOn 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.\n\n[samples]\n\n## Note\n\n  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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10125B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}