Description

Vera likes hiking, so she wants to build her own road network. The road network contains $v$ locations, numbered $1,2,\ldots,v$. The network consists of $e$ undirected roads connecting $a_i$ and $b_i$. The graph is guaranteed to be connected, and multiple edges are allowed.

Vera calls two locations $a,b$ with $a < b$ a perfect pair if there exists a walk that starts from $a$, goes to $b$, and then returns to $a$, such that each road is traversed at most once.

Vera thinks her road network is beautiful if it contains exactly $k$ perfect pairs.

Given $k$, help Vera find a beautiful road network.

Input Format

The input contains one line with an integer $k$.

Output Format

Output a beautiful road network in the following format:

• The first line contains the number of vertices $v$ and the number of edges $e$.
• The next $e$ lines each contain two integers $a_i$ and $b_i$, indicating that there is an edge between $a_i$ and $b_i$ ($1 \le i \le e$).

The order of the edges does not matter. If there are multiple beautiful road networks, you may output any one of them.

2

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

6

4 4
1 2
2 3
3 4
4 1

Hint

Sample Explanation

For sample $1$, the perfect pairs are 1,2 and 3,4.

For sample $2$, every pair of vertices is a perfect pair.

Constraints and Notes

This problem uses bundled testdata, with a total of $3$ subtasks.

• Subtask 1 (12 points): $0 \le k \le 10^3$.
• Subtask 2 (24 points): $0 \le k \le 10^5$.
• Subtask 3 (64 points): $0 \le k \le 10^7$.

For all testdata, it is guaranteed that $0 \le k \le 10^7$ and $1 \le v,e \le 5 \times 10^3$.

Source: CCO 2017 Day 1 “Vera and Trail Building”.

Note: This translation is from LOJ.

Translated by ChatGPT 5