题目描述

这是一道交互题。

给定一棵树 $T$，我们定义这棵树上的某个点集 $S$ 的最小连通块为包含这个点集中所有点的最小的树上连通块。

给定一棵树的大小 $n$，你可以进行若干次询问，每次询问你可以给出一个点集 $S$ 和这棵树上的一个点 $x$，交互库会返回一个布尔值 $x$ 表示是否在点集 $S$ 的最小连通块上。你需要确定这棵树的形态。

实现细节

你的程序中需引用 C.hpp。

你需要实现下面的函数：

std::vector<std::pair<int, int> > work(int n)

其中 n 表示这棵树的大小 $n$，也就是题面描述中的 $n$。

你返回的 std::vector<std::pair<int, int> > 中每个 std::pair<int, int> 表示树的一条边的两个端点，你需要保证返回的 std::vector<std::pair<int, int> > 的大小为 $n-1$ 且构成一棵树，否则你的程序将得到 $0$ 分。

你可以调用以下函数和交互库进行交互：

bool ask(std::vector<int> S, int x)

其中 S 表示你给出的点集 $S$，也就是题面描述中的 $S$；x 表示你给出的点 $x$，也就是题面描述中的 $x$。你需要保证 $S$ 不为空，且 $S$ 中的点和 $x$ 在 $[1, n]$ 上，否则你的程序将得到 $0$ 分。如果在 $x$ 的最小连通块 $S$ 上则返回值为 true 否则返回值为 false。

详情可以参见下发的示例代码。

请注意：交互函数所需的时间复杂度为 $O(|S|)$，你可能会因为你给定的过大而导致超时。

测试程序方式

评测程序示例将读入如下格式的输入数据：

第一行包括一个正整数 $n$，表示这棵树的大小。接下来 $n-1$ 行，每行两个整数 $x, y$，表示一条边的两个端点。点的编号从 $\mathbf 1$ 开始。

评测程序示例将返回你的错误信息或以如下格式返回：

Your answer is correct.You made AAA queries with total size BBB.

其中 AAA 表示你的询问次数，BBB 表示你询问给定的点集的总大小。

5
1 2
1 3
2 4
2 5

Your answer is correct.You made 0 queries with total size 0.

数据范围与提示

本题共有一个测试包，内含若干个测试点。

对于每个测试点，若你的程序有不合法的询问或返回，或返回的树的形态不正确，则你在该测试点获得 $0$ 分，否则令 $step$ 表示你的程序的询问次数，则你在该测试点获得的分数将评定为 $\min(\lfloor \frac{2.2\times 10^6}{step} \rfloor, 100)$。

你所获得的这道题的分数即为所有数据点的分数的最小值。

对于所有数据，均满足 $n=1000$。