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

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

题目描述

译自 CCO 2017 Day1「Vera and Trail Building

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

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

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

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

输入格式

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

输出格式

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

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

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

样例

样例输入 1

2

样例输出 1

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

样例解释 1

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

样例输入 2

6

样例输出 2

4 4
1 2
2 3
3 4
4 1

样例解释 2

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

数据范围与提示

对于 12%12\% 的测试点,K1000K\le 1000
对于另 24%24\% 的测试点,K105K\le 10^5
对于全部数据,0<K1070\lt K\le 10^7