P6342 [CCO 2017] Vera and Trail Building

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.

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

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.

#### 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](https://cemc.math.uwaterloo.ca/contests/computing/2017/index.html) Day 1 “[Vera and Trail Building](https://cemc.math.uwaterloo.ca/contests/computing/2017/stage%202/day1.pdf)”. Note: This translation is from [LOJ](https://loj.ac/problem/2750). Translated by ChatGPT 5