{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"Input contains a signle integer s. (0 ≤ s ≤ 105)"},{"iden":"output","content":"Print \"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."},{"iden":"examples","content":"Input1Output2 11 2Input2OutputImpossibleInput3Output3 31 22 33 1Input48Output7 61 21 32 42 53 63 7"},{"iden":"note","content":"A 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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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.","simple_statement":"Given an integer s, find a simple connected graph where the sum of shortest path lengths between all pairs of vertices equals s.  \nIf impossible, print \"Impossible\".  \nOtherwise, print the number of vertices n and edges m, followed by m edges (u, v).","has_page_source":false}