您目前正在研究一种称为深度优先搜索 (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 的说明
下图描述了此示例的输出。