#2750. 「CCO 2017」Vera 与道路建设

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Anfangen

题目描述

译自 CCO 2017 Day1「Vera and Trail Building

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

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

她并不想让她的公路网变得过大,所以公路应该满足 1≤V,E≤50001\le V,E\le 50001V,E5000

给定 KKK,帮 Vera 找到美丽公路网。

输入格式

输入只有一行,为一个整数 KKK

输出格式

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

  • 第一行为顶点的数量 VVV 与边数 EEE
  • 下面的 EEE 行每行应包含代表从 aia_iaibib_ibi 有一条边的两个整数 aia_iaibib_ibi (1≤i≤E)(1 \le i \le E)(1iE)

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

样例

样例输入 1

2

样例输出 1

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

样例解释 1

对于样例 111,完美点对为 1,21,21,23,43,43,4

样例输入 2

6

样例输出 2

4 4
1 2
2 3
3 4
4 1

样例解释 2

对于样例 222,每个点对都是完美点对。

数据范围与提示

对于 12%12\%12% 的测试点,K≤1000K\le 1000K1000
对于另 24%24\%24% 的测试点,K≤105K\le 10^5K105
对于全部数据,0<K≤1070\lt K\le 10^70<K107