401820: GYM100534 C Coin Graph

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 between all pairs of its vertices is s.

Input contains a signle integer s. (0 ≤ s ≤ 10⁵)

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 u_i, v_i(1 ≤ u_i, v_i ≤ n, u_i ≠ v_i) — two vertices, connected by an edge in the resulting graph. If there are several answers you can print any of them.

1

2 1
1 2

2

Impossible

3

3 3
1 2
2 3
3 1

48

7 6
1 2
1 3
2 4
2 5
3 6
3 7

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.