Canadian Computing Olympiad: 2017 Day 1, Problem 1

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 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\le V,E\le 5000$.

Given $K$, help Vera find any beautiful trail network.

Input Specification

There is one line of input, which contains the integer $K$ $(0<K\le {10}^7)$.
For 3 of the 25 available marks, $K\le 1000$.
For an additional 6 of the 25 available marks, $K\le {10}^5$.

Output Specification

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\le i\le 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 that a solution always exists.

Sample Input 1

2

Sample Output 1

4 5
1 2
2 1
3 4
4 3
1 4

Explanation for Sample Output 1

The two beautifully connected pairs are 1, 2 and 3, 4.

Sample Input 2

6

Sample Output 2

4 4
1 2
2 3
3 4
4 1

Explanation for Sample Output 2

All pairs of places form a beautifully connected pair.