Vera and Trail Building

Vera loves hiking and is building her own trail network. The network has $V$ places numbered $1$ to $V$ and $E$ bidirectional trails, where trail $i$ directly joins two distinct places $a_i$ and $b_i$. The network has to be connected, so it is possible to hike between any two places along the trails. More than one trail may directly join the same pair of places.

Two places $a$ and $b$ with $a < b$ form a beautifully connected pair if Vera can hike from $a$ to $b$ and then back to $a$ without hiking on the same trail more than once. Vera calls her network beautiful if it has exactly $K$ beautifully connected pairs.

Vera does not want her network to be too large, so it has to satisfy $1 \le V, E \le 5000$.

For almost every $K$ many beautiful networks exist, so this problem asks for one specific network. The output section states exactly which one to print.

The first line contains one integer $K$ ($1 \le K \le 10^7$).

Build the network with the rule below and print it. Nothing else is accepted.

First split $K$ into blocks. Start with an empty list and repeat while $K > 0$: take the largest integer $m$ with $m \ge 2$ and $m(m-1)/2 \le K$, append $m$ to the list, then replace $K$ by $K - m(m-1)/2$. Call the resulting list $m_1, m_2, \dots, m_t$ and let $V = m_1 + m_2 + \dots + m_t$.

Number the places $1$ to $V$ and give every block a consecutive range of places: block $1$ takes places $1$ to $m_1$, block $2$ takes the next $m_2$ places, and so on. Write $s_j$ for the first place of block $j$ and $e_j$ for its last place.

The first line of the output contains $V$ and $E = V + t - 1$, separated by one space. Each of the next $E$ lines contains the two places of one trail, separated by one space, in the order described here.

For $j = 1, 2, \dots, t$, print the trails of block $j$:

• if $m_j = 2$, print the line "$s_j$ $e_j$" twice;
• if $m_j \ge 3$, print the $m_j$ trails $(s_j, s_j + 1)$, $(s_j + 1, s_j + 2)$, up to $(e_j - 1, e_j)$, and then $(e_j, s_j)$, one per line, each with its first place written first.

After the trails of all $t$ blocks, print the $t - 1$ joining trails: for $j = 2, 3, \dots, t$, print the line "$e_{j-1}$ $s_j$".

This network is connected, has exactly $K$ beautifully connected pairs, and satisfies $V \le 4587$ and $E \le 4592$ for every allowed $K$.

In the first example $K = 2$, so the blocks are $m_1 = 2$ and $m_2 = 2$. Places $1$ and $2$ are joined by two trails, places $3$ and $4$ are joined by two trails, and the trail between places $2$ and $3$ joins the two blocks. The two beautifully connected pairs are $(1, 2)$ and $(3, 4)$.

In the second example $K = 6$, so there is one block with $m_1 = 4$ and the network is a cycle on four places. All six pairs of places form a beautifully connected pair.