题目背景

在洛谷上提交时，只需要提交一个文件。

不要引入 alice.h 和 bob.h。在文件头加入以下内容：

long long setN(int n);

只支持 C++17 / C++20 提交。

题目描述

Alice 和 Bob 是著名的魔术师。Catherine 是一位富豪，她非常喜欢观看 Alice 和 Bob 的魔术。某一天，Catherine 决定向 Alice 和 Bob 发出挑战：只要他们能成功表演如下的魔术，Catherine 就将向他们提供巨额奖金！这个魔术的表演过程如下：

• 步骤 $1$：Bob 进⼊⼀个密室中，在魔术的全程中，他只能与 Catherine 交流。接下来，Alice 告诉 Catherine ⼀个在 $2$ 到 $5000$ 之间的整数 $n$。
• 步骤 $2$：Catherine 告诉 Alice ⼀个在 $1$ 到 $10^{18}$ 之间的整数 $X$。
• 步骤 $3$：Alice 生成⼀个具有 $n$ 个节点的树，并告诉 Catherine。
• 步骤 $4$：Catherine 删除树中的⼀些边（至多 $\left\lfloor\dfrac{n-2}{2}\right\rfloor$ 条），并将剩余的边告诉 Bob。
• 步骤 $5$：Bob 根据 Catherine 给出的信息，猜出 Catherine 告诉 Alice 的数是多少。

然⽽，Alice 和 Bob 被这个魔术难倒了，于是他们不得不寻求你的帮助。请你写一段程序，实现 Alice 和 Bob 的策略，以帮助他们赢得 Catherine 的挑战。

通信方式：

你需要实现两个函数

1. std::vector<std::pair<int, int>> Alice();

• 对于每组测试数据，这个函数只会被调用⼀次。
• 函数应当返回⼀个含有 pair<int, int> 类型的 vector，表示 Alice 在魔术的步骤 3 中生成的树的边集。
  • 注意树中的节点应当从 1 开始编号。
  • 你需要确保函数返回的树是符合规范的，也就是说，树中应当恰好包含 n − 1 条边，且所有节点彼此连通。

函数 Alice() 应当调用如下函数恰好⼀次：

long long setN(int n);

• 这个函数表示，在魔术的步骤 1 中，Alice 选择⼀个数 $n$ 告诉 Catherine。
• 函数返回⼀个数 $X$，表示 Catherine 在魔术的步骤 2 中告诉 Alice 的数。

---

2. long long Bob(std::vector<std::pair<int, int>> V);

• 对于每组测试数据，这个函数只会被调用⼀次，且⼀定是在调用 Alice() 之后。
• $V$ 表⽰在魔术的步骤 4 中，Catherine 告诉 Bob 的边集。
• 上述边集是有序的，具体而言：
  • 对于⼀条边的两个端点而言，编号较⼩的端点靠前；
  • 所有的边按照第⼀个端点为第⼀关键字、第⼆个端点为第⼆关键字的顺序升序排序。
• 函数应当返回⼀个整数 $X$，表⽰ Bob 在魔术的步骤 5 中给出的回答。

输入格式

无

输出格式

无

提示

例子

考虑下面的调用： 调用函数| 返回值 :-:|:-: Alice()| setN(4)| $3$ ||$\{\{1, 2\}, \{2, 3\}, \{2, 4\}\}$ Bob({{1,2},{2,4}})| $3$ 该样例代表了以下场景：

• 步骤 1：最开始，Alice 将数字 $4$ 告诉 Catherine。
• 步骤 2：Catherine 将数字 $3$ 告诉 Alice。
• 步骤 3：Alice 生成了⼀棵具有 $4$ 个节点的树，其边集为 $\{\{1, 2\}, \{2, 3\}, \{2, 4\}\}$，将这棵树告诉 Catherine。
• 步骤 4：Catherine 删去了树中连接节点 $2$ 和 $3$ 的边，并把剩余的边 $\{\{1, 2\}, \{2, 4\}\}$ 告诉 Bob。
• 步骤 5：Bob 给出数字 $3$ 作为回答。由于他给出了正确答案，他们的魔术表演⼤获成功。

子任务

1. (5 分)：$X\leq 5, 000$。
2. (30 分)：$X\leq25, 000, 000$。
3. (65 分)：没有特殊限制。