PEG Judge - CCO17 - Vera and Trail Building

2017 Canadian Computing Olympiad

Day 1, Problem 1 - Vera and Trail Building

Vera loves hiking and is going to build her own trail network. It will consist of V places numbered from 1 to V, and E bidirectional trails, where the i-th trail directly joins two distinct places a_i and b_i. Vera would like her network to be connected so it should be possible to hike between any two places using the trails. It is possible that there could be more than one trail directly joining the same pair of places.

Vera considers two places a, b with a < b to form a beautifully connected pair if it is possible to hike using the trails from a to b then back to a without hiking on the same trail more than once. She thinks that her trail network would be beautiful if it had exactly K beautifully connected pairs.

Vera does not want her network to be too large, so the network should satisfy 1 ≤ V, E ≤ 5000.

Given K, help Vera find any beautiful trail network.

Input format

There is one line of input, which contains the integer K (0 < K ≤ 10⁷).
For 3 of the 25 available marks, K ≤ 1000.
For an additional 6 of the 25 available marks, K ≤ 10⁵.

Output format

Print a beautiful network in the following format:

the first line should contain the number of vertices, V, followed by one space, followed by the number of edges, E;
each of the next E lines should contain two integers, a_i and b_i, separated by one space, indicating a trail between places a_i and b_i (1 ≤ i ≤ E).

The trails can be printed in any order. The two places of any trail can be printed in any order. If there are multiple beautiful trail networks, print any of them. It is guaranteed a solution always exists.