← 返回题目列表

Codeforces · 959/C

C. Mahmoud 和 Ehab 以及错误的算法

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

Mahmoud 试图解决树上的顶点覆盖问题。问题陈述是:

给定一个由 n 个节点组成的无向树,找到覆盖所有边的最小顶点数。形式上,我们需要找到一组顶点,使得对于属于树的每条边 (u, v),要么 u 在集合中,要么 v 在集合中,或者两者都在集合中。 Mahmoud 发现了以下算法:

- 树的根位于节点 1。
- 计算偶数深度的节点数。让它为evenCnt。
- 计算奇数深度处的节点数。让它为oddCnt。
- 答案是 EvenCnt 和 oddCnt 之间的最小值。

树中节点的深度是该节点与根之间的最短路径中的边数。根的深度为0。

Ehab 告诉 Mahmoud 这个算法是错误的,但他不相信,因为他已经在很多树上测试了他的算法并且它有效,所以 Ehab 让你找到 2 棵由 n 个节点组成的树。该算法应该为第一棵树找到错误答案,为第二棵树找到正确答案。

输入

唯一一行包含一个整数 n (2 ≤ n ≤ 105),即所需树中的节点数。

输出

输出应由 2 个独立的部分组成,每个部分包含一棵树。该算法应该为第一部分中的树找到错误答案,并为第二部分中的树找到正确答案。如果某些部分不存在树,则仅针对该部分输出“-1”(不带引号)。

如果某个部分的答案存在,则它应包含 n - 1 行,每行包含 2 个空格分隔的整数 u 和 v (1 ≤ u, v ≤ n),这意味着节点 u 和节点 v 之间存在无向边。如果给定的图不是树或不遵循格式,您将收到错误的答案判定。

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

示例

输入 #1

2

输出 #1

-1
1 2

输入 #2

8

输出 #2

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

注意

在第一个示例中,只有 1 棵树,有 2 个节点(节点 1 连接到节点 2)。该算法将在其中产生正确的答案,因此我们在第一部分中打印了 - 1,但请注意我们在第二部分中打印了这棵树。

在第二个示例中:

在第一棵树中,算法将找到具有 4 个节点的答案,而存在像这样的具有 3 个节点的答案: 在第二棵树中,算法将找到具有 3 个节点的答案,这是正确的: