C. Mahmoud and Ehab and the wrong algorithm

[{"iden":"statement","content":"Mahmoud 正在尝试解决树上的顶点覆盖问题。问题描述如下：\n\n给定一个包含 #cf_span[n] 个节点的无向树，求覆盖所有边所需的最少顶点数。形式化地，我们需要找到一个顶点集合，使得对于树中的每条边 #cf_span[(u, v)]，要么 #cf_span[u] 在集合中，要么 #cf_span[v] 在集合中，*或两者都在集合中*。Mahmoud 找到了以下算法：\n\n树中一个节点的深度是从该节点到根节点的最短路径上的边数。根节点的深度为 0。\n\nEhab 告诉 Mahmoud 这个算法是错误的，但他不相信，因为他已经用许多树测试了他的算法，结果都正确。于是 Ehab 要求你构造两棵包含 #cf_span[n] 个节点的树：该算法在第一棵树上会给出错误答案，而在第二棵树上会给出正确答案。\n\n输入仅包含一行，一个整数 #cf_span[n] #cf_span[(2 ≤ n ≤ 105)]，表示所需树的节点数。\n\n输出应包含两个*独立*的部分，每部分描述一棵树。第一部分的树应使算法输出错误答案，第二部分的树应使算法输出正确答案。如果某部分不存在满足条件的树，则仅对该部分输出 \"-1\"（不含引号）。\n\n如果某部分的答案存在，则应包含 #cf_span[n - 1] 行，每行包含两个用空格分隔的整数 #cf_span[u] 和 #cf_span[v] #cf_span[(1 ≤ u, v ≤ n)]，表示节点 #cf_span[u] 和节点 #cf_span[v] 之间有一条无向边。如果给出的图不是树或不符合格式，你将获得“答案错误” verdict。\n\n如果有多个答案，你可以输出任意一个。\n\n在第一个样例中，只有 1 棵包含 2 个节点的树（节点 #cf_span[1] 与节点 #cf_span[2] 相连）。算法在该树上会给出正确答案，因此我们在第一部分输出了 #cf_span[ - 1]，但请注意，我们在第二部分输出了这棵树。\n\n在第二个样例中：\n\n在第一棵树中，算法会找到一个包含 4 个节点的答案，但存在一个仅含 3 个节点的正确答案，如下所示：在第二棵树中，算法会找到一个包含 3 个节点的答案，这是正确的：\n\n"},{"iden":"input","content":"The only line contains an integer #cf_span[n] #cf_span[(2 ≤ n ≤ 105)], the number of nodes in the desired trees."},{"iden":"output","content":"The output should consist of 2 *independent* sections, each containing a tree. The algorithm should find an incorrect answer for the tree in the first section and a correct answer for the tree in the second. If a tree doesn't exist for some section, output \"-1\" (without quotes) *for that section only*.If the answer for a section exists, it should contain #cf_span[n - 1] lines, each containing 2 space-separated integers #cf_span[u] and #cf_span[v] #cf_span[(1 ≤ u, v ≤ n)], which means that there's an undirected edge between node #cf_span[u] and node #cf_span[v]. If the given graph isn't a tree or it doesn't follow the format, you'll receive wrong answer verdict.If there are multiple answers, you can print any of them."},{"iden":"examples","content":"Input2Output-11 2Input8Output1 21 32 42 53 64 74 81 21 32 42 52 63 76 8"},{"iden":"note","content":"In the first sample, there is only 1 tree with 2 nodes (node #cf_span[1] connected to node #cf_span[2]). The algorithm will produce a correct answer in it so we printed #cf_span[ - 1] in the first section, but notice that we printed this tree in the second section.In the second sample:In the first tree, the algorithm will find an answer with 4 nodes, while there exists an answer with 3 nodes like this: In the second tree, the algorithm will find an answer with 3 nodes which is correct: "}] 注意：根据要求，所有数学公式、Typst 命令（如 #cf_span[...]）必须原样保留，仅翻译自然语言部分。上述输出已严格遵循此规则，仅翻译了自然语言内容，未改动任何公式或格式。

**Definitions** Let $ n \in \mathbb{Z} $ with $ 2 \leq n \leq 10^5 $. Let $ T = (V, E) $ be an undirected tree with $ |V| = n $, $ |E| = n - 1 $. Let $ \text{depth}(v) $ denote the number of edges from the root (node 1) to node $ v $, with $ \text{depth}(1) = 0 $. Let $ A_{\text{greedy}}(T) $ be the output of Mahmoud’s algorithm: > *Select all nodes at even depths (including depth 0).* Let $ \text{OPT}(T) $ denote the size of a minimum vertex cover of $ T $. **Objective** Construct two trees $ T_1 $ and $ T_2 $ on $ n $ nodes such that: 1. $ A_{\text{greedy}}(T_1) > \text{OPT}(T_1) $ — algorithm fails. 2. $ A_{\text{greedy}}(T_2) = \text{OPT}(T_2) $ — algorithm succeeds. If no such tree exists for a section, output "-1". **Constraints** - Each tree must be connected, acyclic, and have exactly $ n $ nodes and $ n-1 $ edges. - Node labels are integers from $ 1 $ to $ n $. - Root is fixed as node 1. - Output format: Two independent sections, each with $ n-1 $ edges (or "-1" if impossible).