P6342 [CCO 2017] Vera 与道路建设

Vera 喜欢远足，因此她要建立自己的公路网。公路网包含 $v$ 个地点，这些地点分别编号为 $1,2,...,v$。公路网由 $e$ 条连接 $a_i$ 和 $b_i$ 的双向道路组成。保证图联通，允许有重边。 Vera 认为满足先从 $a$ 走到 $b$ 然后再回到 $a$，使得每条道路被通过不超过一次且满足 $a < b$ 的两个地点 $a,b$ 是一对 **完美点对**。她认为如果公路网恰好包含 $k$ 个完美点对，那么她的公路网就是美丽的。 给定 $k$，帮 Vera 找到美丽公路网。

输入只有一行，为一个整数 $k$。

按照以下格式输出一个美丽公路网： - 第一行为顶点的数量 $v$ 与边数 $e$； - 下面的 $e$ 行每行应包含代表从 $a_i$ 至 $b_i$ 有一条边的两个整数 $a_i$ 与 $b_i$（$1 \le i \le e$）。 道路的输出顺序无关紧要。如果有多个美丽公路网，你可以输出它们中的任意一个。

#### 样例解释 对于样例 $1$，完美点对为 `1,2` 和 `3,4`。 对于样例 $2$，每个点对都是完美点对。 #### 数据范围及约定 **本题采用多测试点捆绑测试，共有 $3$ 个子任务。** - 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$。 对于全部的测试点，保证 $0 \le k \le 10^7$，$1 \le v,e \le 5 \times 10^3$。 来源：[CCO 2017](https://cemc.math.uwaterloo.ca/contests/computing/2017/index.html) Day1「[Vera and Trail Building](https://cemc.math.uwaterloo.ca/contests/computing/2017/stage%202/day1.pdf)」。 说明：翻译来自 [LOJ](https://loj.ac/problem/2750)。