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 个节点的答案,这是正确的: