{"problem":{"name":"E. Connecting Components","description":{"content":"You are given an undirected graph with $n$ nodes and $n -1$ edges. The graph doesn't contain loops or multiple edges. You are allowed to make the following operation *at most twice*: In other words,","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":10000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10196E"},"statements":[{"statement_type":"Markdown","content":"You are given an undirected graph with $n$ nodes and $n -1$ edges. The graph doesn't contain loops or multiple edges.\n\nYou are allowed to make the following operation *at most twice*:\n\nIn other words, you are allowed to change one endpoint of an edge in one move, and the cost of this move is the absolute difference between the new ID and the old ID of the changed endpoint. \n\nFind the minimum total cost needed to make the given graph connected in *at most two* moves, or determine that it is impossible.\n\nNote that you do *not* have to minimize the number of moves.\n\nThe first line of input contains a single integer $T$ ($1 <= T <= 10^4$), the number of test cases.\n\nThe first line of each test case contains a single integer $n$ ($1 <= n <= 10^5$), the number of nodes in the graph.\n\nEach of the following $n -1$ lines contains two space-separated integers $u$ and $v$ ($1 <= u, v <= n$, $u eq.not v$), representing an edge that connects the nodes $u$ and $v$. Each pair of nodes will be connected by at most one edge.\n\nThe sum of $n$ over all test cases doesn't exceed $5 times 10^6$.\n\nFor each test case, if it is impossible to make the given graph connected in *at most two* moves, output $-1$. Otherwise, output the minimum total cost needed, in a single line.\n\n## Input\n\nThe first line of input contains a single integer $T$ ($1 <= T <= 10^4$), the number of test cases.The first line of each test case contains a single integer $n$ ($1 <= n <= 10^5$), the number of nodes in the graph.Each of the following $n -1$ lines contains two space-separated integers $u$ and $v$ ($1 <= u, v <= n$, $u eq.not v$), representing an edge that connects the nodes $u$ and $v$. Each pair of nodes will be connected by at most one edge.The sum of $n$ over all test cases doesn't exceed $5 times 10^6$.\n\n## Output\n\nFor each test case, if it is impossible to make the given graph connected in *at most two* moves, output $-1$. Otherwise, output the minimum total cost needed, in a single line.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ be the number of nodes.  \n- Let $ G = (V, E) $ be an undirected graph with $ V = \\{1, 2, \\dots, n\\} $ and $ |E| = n - 1 $.  \n- Let $ C = \\{ c_1, c_2, \\dots, c_k \\} $ be the connected components of $ G $, with $ k \\geq 2 $ (since $ G $ is a forest with $ n - 1 $ edges and $ n $ nodes, it is disconnected iff $ k > 1 $).\n\n**Constraints**  \n1. $ 1 \\leq T \\leq 10^4 $  \n2. $ 1 \\leq n \\leq 10^5 $  \n3. Sum of all $ n $ across test cases $ \\leq 5 \\times 10^6 $  \n4. Each edge connects distinct nodes; no multiple edges or self-loops.  \n5. Each move: select one edge $ (u, v) \\in E $ and change one endpoint $ u \\to u' $ or $ v \\to v' $, where $ u', v' \\in \\{1, 2, \\dots, n\\} $, $ u' \\ne v' $, and cost = $ |u' - u| $ or $ |v' - v| $.  \n6. At most two moves allowed.  \n\n**Objective**  \nFind the minimum total cost to make $ G $ connected using at most two moves, or output $ -1 $ if impossible.  \n\nLet $ k $ be the number of connected components in $ G $.  \n- If $ k = 1 $: cost = 0.  \n- If $ k \\geq 4 $: impossible → output $ -1 $.  \n- If $ k = 2 $:  \n  - Option 1: One move connecting two components: minimize $ |u' - u| $ over all $ u \\in C_i $, $ v \\in C_j $, $ u' \\in C_j $, $ v' \\in C_i $ such that replacing $ u $ with $ v $ (or vice versa) connects components.  \n  - Option 2: Two moves: reassign endpoints of two edges to connect all components; minimize sum of absolute differences.  \n- If $ k = 3 $:  \n  - Must use exactly two moves to connect three components.  \n  - Find two edges and reassign endpoints to merge all three components with minimal total cost.  \n\nDefine:  \n- Let $ \\mathcal{C} = \\{C_1, \\dots, C_k\\} $ be the connected components.  \n- For each component $ C_i $, let $ S_i \\subseteq \\{1, \\dots, n\\} $ be its set of node labels.  \n- For $ k = 2 $:  \n  $$\n  \\min_{\\substack{u \\in S_1 \\\\ v \\in S_2}} \\min\\left( |v - u|, \\min_{\\substack{u' \\in S_2 \\\\ v' \\in S_1}} (|u' - u| + |v' - v|) \\right)\n  $$\n  (but only one move allowed for one-edge fix; two moves only if one move insufficient — but one move suffices if any $ u \\in S_1 $, $ v \\in S_2 $ can be matched by changing one endpoint).  \n  Actually: one move: pick edge $ (x, y) $, change $ x $ to some $ x' \\in S_2 $, cost $ |x' - x| $. Need $ x \\in S_1 $, $ y \\in S_2 $, and $ x' \\in S_2 $, so $ x' \\ne y $, and $ x' \\in S_2 \\setminus \\{y\\} $.  \n  So for $ k = 2 $:  \n  $$\n  \\min_{\\substack{(x,y) \\in E \\\\ x \\in S_1, y \\in S_2}} \\min_{\\substack{x' \\in S_2 \\\\ x' \\ne y}} |x' - x|\n  $$\n  or similarly change $ y \\to y' \\in S_1 $.  \n\n- For $ k = 3 $:  \n  Must use two moves. Each move changes one endpoint of one edge. Goal: merge three components into one.  \n  Consider all pairs of edges $ e_1, e_2 \\in E $, and all possible reassignments:  \n  Change one endpoint of $ e_1 $ to connect two components, and one endpoint of $ e_2 $ to connect the third.  \n  Or both moves connect to a common component.  \n\nFormally:  \nLet $ \\mathcal{P} $ be the set of all pairs of edges $ (e_1, e_2) $, and for each, consider all valid reassignments of one endpoint per edge to node IDs in other components such that the graph becomes connected.  \nCompute minimal total cost over all such valid reassignments.  \n\n**Output**  \nFor each test case:  \n$$\n\\begin{cases}\n0 & \\text{if } k = 1 \\\\\n\\min \\text{ cost over 1 or 2 moves} & \\text{if } k = 2 \\text{ or } k = 3 \\\\\n-1 & \\text{if } k \\geq 4\n\\end{cases}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10196E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}