← 返回题目列表

Codeforces · 1178/D

D. 素图

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

每个人都喜欢素数。爱丽丝是一个人,因此她也分享对他们的爱。鲍勃想送她一份深情的礼物,但想不出什么有创意的礼物。因此,他会给她一张图表。多么原创啊,鲍勃!爱丽丝一定会很兴奋!

在构建图表时,他需要满足四个条件:

- 它必须是一个简单的无向图,即没有多个(平行)边和自循环。
- 顶点数必须恰好为 $$$n$$$ — 他选择的数字。这个数不一定是素数。
- 边的总数必须是质数。
- 每个顶点的度数(即连接到顶点的边数)必须是素数。

下面是 $$$n = 4$$$ 的示例。第一张图(左图)无效,因为顶点 $$$2$$$ (和 $$$4$$$)的度数等于 $$$1$$$,这不是素数。第二张图(中间一张)无效,因为边的总数为 $$$4$$$,这不是素数。第三张图(右图)是 $$$n = 4$$$ 的有效答案。

请注意,该图可以断开连接。

请帮助鲍勃找到任何这样的图!

输入

输入由单个整数 $$$n$$$ ($$$3 \leq n \leq 1\,000$$$) 组成 - 顶点数。

输出

如果没有满足条件的图形,则打印包含整数 $$$-1$$$ 的单行。

否则,首先打印一行包含素数 $$$m$$$ ($$$2 \leq m \leq \frac{n(n-1)}{2}$$$) — 图中的边数。然后,打印 $$$m$$$ 行,其中第 $$$i$$$ 包含两个整数 $$$u_i$$$、$$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) — 意味着顶点 $$$u_i$$$ 和 $$$v_i$$$ 之间有一条边。每个顶点的度数必须是素数。不得有多个(平行)边或自环。

如果有多个解决方案,您可以打印其中任何一个。

请注意,该图可以断开连接。

示例

输入 #1

4

输出 #1

5
1 2
1 3
2 3
2 4
3 4

输入 #2

8

输出 #2

13
1 2
1 3
2 3
1 4
2 4
1 5
2 5
1 6
2 6
1 7
1 8
5 8
7 8

注意

声明中描述了第一个示例。

在第二个示例中,顶点的度数为 $$$[7, 5, 2, 2, 3, 2, 2, 3]$$$。这些数字中的每一个都是质数。此外,边的数量 $$$13$$$ 也是素数,因此两个条件都满足。