{"problem":{"name":"C. Coin Graph","description":{"content":"First of all you must know that the name of this problem is irrelevant to what we want! You are given an integer s. Find a simple connected graph such that the sum of lengths of the shortest paths be","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10053C"},"statements":[{"statement_type":"Markdown","content":"First of all you must know that the name of this problem is irrelevant to what we want!\n\nYou are given an integer s. Find a simple connected graph such that the sum of lengths of the shortest paths between all pairs of its vertices is s.\n\nInput contains a signle integer s. (0 ≤ s ≤ 105)\n\nPrint \"Impossible\" (without the quotes) if there is no graph, satisfying the described conditions.   Otherwise in the first line print two space-separated integers n and m — the number of vertices and edges in your graph, respectively. Each of following m lines contain two space-separated integers ui, vi(1 ≤ ui, vi ≤ n, ui ≠ vi) — two vertices, connected by an edge in the resulting graph.  If there are several answers you can print any of them.\n\nA graph is simple if it has no self-loops or multiple edges between the same vertices. All edges in a simple graph are unweighted and undirected.   A graph is connected if there is a path connecting every pair of vertices.\n\n## Input\n\nInput contains a signle integer s. (0 ≤ s ≤ 105)\n\n## Output\n\nPrint \"Impossible\" (without the quotes) if there is no graph, satisfying the described conditions.   Otherwise in the first line print two space-separated integers n and m — the number of vertices and edges in your graph, respectively. Each of following m lines contain two space-separated integers ui, vi(1 ≤ ui, vi ≤ n, ui ≠ vi) — two vertices, connected by an edge in the resulting graph.  If there are several answers you can print any of them.\n\n[samples]\n\n## Note\n\nA graph is simple if it has no self-loops or multiple edges between the same vertices. All edges in a simple graph are unweighted and undirected.   A graph is connected if there is a path connecting every pair of vertices.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ s \\in \\mathbb{Z} $ with $ 0 \\leq s \\leq 10^5 $.  \n\n**Objective**  \nFind a simple connected graph $ G = (V, E) $ such that the sum of the lengths of all shortest paths between every pair of distinct vertices equals $ s $, i.e.,  \n$$\n\\sum_{\\{u,v\\} \\subseteq V, u \\neq v} \\text{dist}(u,v) = s\n$$  \nIf no such graph exists, output \"Impossible\".  \n\nOtherwise, output:  \n- $ n = |V| $, $ m = |E| $  \n- $ m $ edges $ (u_i, v_i) $, with $ 1 \\leq u_i < v_i \\leq n $, forming a simple connected graph.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10053C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}