← 返回题目列表

AtCoder · ttpc2023_k

K. 密植

中文机器翻译题面 查看原题

配点 : 100 点

問題文

整数 K 。创建一个边尽可能少的无向图,满足以下条件: 1 请构建一个。

  • 顶点数 N 是 1 以上 100 以下
  • 边数 M 是 10^5 以下
  • 当我们假设所有边都是可区分的时,图的生成树恰好是 K 存在。也就是说,M 如何从书本的边缘中选择一些边缘 2^M 在街道中,如果删除其他边,图形将变成一棵树。 K 存在。

制約

  • K 是整数
  • 1 \le K \le 10^9

得点

当程序产生的输出满足所有测试用例中问题陈述的条件时,提交为 AC 变为。此时,在所有测试用例中 M 的最大值 以下几点给出为 M_{\max} 。

条件 点数
10^4 < M_{\max} \le 10^5 20 点
10^3 < M_{\max} \le 10^4 60 点
M_{\max} \le 10^3 100 点

入力

输入将以以下形式通过标准输入给出。

K

出力

按以下格式输出满足条件的无向图。如果有多个满足条件的图,则可以输出任意一个。

N M
U_1 V_1
\vdots
U_M V_M

U_i, V_i\ (1 \le i \le M) 是 i 真正的边是顶点 U_i 和顶点 代表连接 V_i 。


入力例 1

11

出力例 1

3 6
1 2
1 3
1 3
2 3
2 3
2 3

输出图如下图所示。

例如,以下 2 选择一条边来创建该图的生成树。

  • 辺 1 - 2 和边缘 由 1 - 3 组成的生成树是 2 街道
  • 辺 1 - 2 和边缘 由 2 - 3 组成的生成树是 3 街道
  • 辺 1 - 3 和边缘 由 2 - 3 组成的生成树是 6 街道

有,所以总共 有 11 生成树。

另外,下图也有一个生成树。 由于存在 11 ,因此以下输出也被认为是正确的。 有一堆

2 11
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2

入力例 2

54

出力例 2

4 10
1 2
2 3
2 3
2 3
3 4
3 4
3 4
4 1
4 1
4 1