配点: 100 点
問題文
PAKEN 市长 E869120 在该市设立了多个检查站。2 我们计划修建几条连接两个检查站的单向道路。
检查点数量 N 和检查点
其编号为 1, 2, 3, ..., N 。
自古以来,这座城市的幸运数字就是 K 。
因此,市长决定建造一些满足以下条件的东西:
- 检查点 到达 1 到 N 的方式正好是 无论您选择哪条路线到达 K 是的。
- 检查点 到达 1 到 N ,您经过的道路数量将保持不变。
例如,K = 5 ,以下检查点和道路布置满足条件。因为检查站
到达 1 到 N 的方式总数为 K = 5 几乎所有方向。 3 因为它遵循书籍的路径。
出于成本考虑,市长应尽可能增加检查站的数量。 我想让 N 尽可能小。
如何构造这样的条件 1 请配置一个。但是,检查点 直接通往 a 到 b 的路是 a < b 除非是,否则不能建造,并且不得建造多条“连接相同两个检查站的道路”。 小于或等于
制約
- K 是 1 以上 10^{18} 的整数
入力
输入是按以下格式从标准输入给出的。
K
出力
输出应采用以下格式。
N M a_1 b_1 a_2 b_2 a_3 b_3 ... a_M b_M
- 1 行显示检查点的数量。 N 和道路数量 请输出 M ,以空格分隔。 请通过
- 2 从行 M 行输出道路信息。然而,a_i, b_i 是“i 第条路是检查站 “直接连接到 a_i 到 b_i ”。此时 必须是 a_i < b_i 。
- 请在末尾添加换行符。
然而,
必须小于或等于N 是 200 。 如果不是,这是一个错误的答案。
另外,(a_i, b_i) \neq (a_j, b_j) (i \neq j) 和 a_i < b_i 。
小課題
小課題 1 [8 点]
- K \leq 150 满意。
小課題 2 [12 点]
- K \leq 8 \ 000 满意。
小課題 3 [80 点]
- 没有其他限制。
然而,小任务 对于 3 ,评分将按如下方式进行。在那里,L 对于所有测试用例 N 的最大值。 对于
- 161 \leq L \leq 200 ,15 点
- 152 \leq L \leq 160 ,55 - (L - 150) * 2 点
- L = 151 ,65 点
- L \leq 150 ,80 点満点
另外,小作业 在 1, 2 中 N \leq 200 被确定是正确的。
入力例 1
5
出力例 1
7 10 1 2 1 3 1 4 2 5 3 5 3 6 4 5 4 6 5 7 6 7
在下图中,检查点 1 到 7 我要去 5 有几种方法,都具有相同数量的方法(3 路),所以满足条件。
入力例 2
20
出力例 2
16 24 1 2 2 3 3 4 5 6 6 7 7 8 9 10 10 11 11 12 13 14 14 15 15 16 1 5 5 9 9 13 2 6 6 10 10 14 3 7 7 11 11 15 4 8 8 12 12 16
在下图中,检查点 1 到 16 我要去 20 有几种方法,都具有相同数量的方法(6 路),所以满足条件。
入力例 3
104
出力例 3
21 75 1 2 1 3 2 4 2 5 2 6 2 7 3 4 3 5 3 6 3 7 4 8 4 9 4 10 4 11 4 12 4 13 4 14 4 15 4 16 4 17 4 18 4 19 4 20 5 8 5 9 5 10 5 11 5 12 5 13 5 14 5 15 5 16 5 17 5 18 5 19 5 20 6 8 6 9 6 10 6 11 6 12 6 13 6 14 6 15 6 16 6 17 6 18 6 19 6 20 7 8 7 9 7 10 7 11 7 12 7 13 7 14 7 15 7 16 7 17 7 18 7 19 7 20 8 21 9 21 10 21 11 21 12 21 13 21 14 21 15 21 16 21 17 21 18 21 19 21 20 21
该输入是 满足 1 约束。