题目描述

译自 CCO 2017 Day1「Vera and Trail Building」

Vera 喜欢远足，因此她要建立自己的公路网。公路网包含 $V$ 个地点，这些地点分别编号为 $1\dots V$。公路网由 $E$ 条连接 $a_i$ 和 $b_i$ 的双向道路组成。保证图联通，允许有重边。

Vera 认为满足先从 $a$ 走到 $b$ 然后再回到 $a$，使得每条道路被通过不超过一次且满足 $a \lt b$ 的两个地点 $a,b$ 是一对「完美点对」。她认为如果公路网恰好包含 $K$ 个完美点对，那么她的公路网就是美丽的。

她并不想让她的公路网变得过大，所以公路应该满足 $1\le V,E\le 5000$。

给定 $K$，帮 Vera 找到美丽公路网。

输入格式

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

输出格式

按照以下格式输出一个美丽公路网：

• 第一行为顶点的数量 $V$ 与边数 $E$；
• 下面的 $E$ 行每行应包含代表从 $a_i$ 至 $b_i$ 有一条边的两个整数 $a_i$ 与 $b_i$ $(1 \le i \le E)$。

道路的输出顺序无关紧要。如果有多个美丽公路网，你可以输出它们中的任意一个。

2

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

6

4 4
1 2
2 3
3 4
4 1

数据范围与提示

对于 $12\%$ 的测试点，$K\le 1000$；
对于另 $24\%$ 的测试点，$K\le 10^5$；
对于全部数据，$0\lt K\le 10^7$。