You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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$）。

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

2

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

6

4 4
1 2
2 3
3 4
4 1

提示

样例解释

对于样例 $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 Day1「Vera and Trail Building」。

说明：翻译来自 LOJ。