← 返回题目列表

Codeforces · 2045/L

L. 越野车 DFS

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

您目前正在研究一种称为深度优先搜索 (DFS) 的图遍历算法。但是,由于错误,您的算法与标准 DFS 略有不同。以下是 Buggy DFS (BDFS) 的算法,假设该图有 $$$N$$$ 个节点(编号从 $$$1$$$ 到 $$$N$$$)。

您意识到该错误使算法比标准 DFS 慢,这可以通过函数 BDFS() 的返回值进行调查。为了研究该算法的行为,您需要通过构造一个无向简单图来制作一些测试用例,以便函数 BDFS() 返回 $$$K$$$,或者确定是否不可能这样做。

输入

由整数 $$$K$$$ ($$$1 \leq K \leq 10^9$$$) 组成的单行。

输出

如果无法构造一个无向简单图使得函数 BDFS() 返回 $$$K$$$,则在一行中输出 -1 -1。

否则,按以下格式输出图形。第一行由两个整数$$$N$$$和$$$M$$$组成,分别表示图中的节点数和无向边数。接下来的$$$M$$$行由两个整数$$$u$$$和$$$v$$$组成,表示连接节点$$$u$$$和节点$$$v$$$的无向边。您可以按任何顺序输出边。该图必须满足以下约束:

- $$$1 \leq N \leq 32\,768$$$
- $$$1 \leq M \leq 65\,536$$$
- $$$1 \leq u, v \leq N$$$,对于所有边。
- 该图是一个简单图,即没有多边也没有自环。

请注意,您不需要最小化节点或边的数量。可以证明,如果可以构造一张BDFS()的返回值为$$$K$$$的图,则存在满足上述所有约束的图。如果有多个解,则可以输出任意一个。

示例

输入 #1

8

输出 #1

3 3
1 2
1 3
2 3

输入 #2

1

输出 #2

-1 -1

输入 #3

23

输出 #3

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

注意

示例输入/输出#1 的说明

左侧的图表描述了该示例的输出。右图描述了该示例的另一个有效解决方案。

示例输入/输出 #3 的说明

下图描述了此示例的输出。