题目描述

给定一棵隐藏的树，它有 N 个顶点（以及 N-1 条边）。你需要恢复这棵树的结构。

你可以提出如下形式的询问：

给定一个顶点集合 S = {v1, …, vk} 和一个特殊顶点 x，其中 2 ≤ k ≤ N。
系统会回答“是”或“否”，表示：是否存在一条包含顶点 x 的简单路径，并且这条路径的两个端点都属于集合 S。

这里，简单路径指的是一条不会重复经过同一个顶点的路径。

你的目标是在尽可能少的询问次数下，找出这棵隐藏树的所有边。

实现细节

你需要实现如下函数：

void solve(int n);

该函数会在每个测试点中被调用一次，参数 n 表示树中顶点的个数 N。顶点编号为 1, 2, ..., N。

评测器会提供如下询问函数：

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

该函数的参数分别为集合 S 和顶点 x。若问题答案为“是”，则返回 true，否则返回 false。

调用 query 时必须满足：

• 所有顶点编号都在 1 到 N 之间；
• S 中的顶点两两不同；
• S 中至少包含 2 个顶点。

在确定整棵树后，你的 solve 函数必须恰好调用 N - 1 次：

void answer(int u, int v);

每次调用 answer(u, v) 表示你认为 (u, v) 是树中的一条边。

• 输出这些边的顺序无关；
• 每条边两个端点的先后顺序也无关。

你的程序还需要包含头文件：

#include "treeq.h"

该头文件中包含上述函数原型。

限制

• 2 ≤ N ≤ 2000

子任务与评分

子任务	分值	额外限制
1	10	N = 50
2	50	N = 250
3	40	N = 2000

若你的程序不能正确恢复整棵树，或者提出了非法询问，则该测试点得分为 0。

对某个测试点，设你所使用的询问次数为 Q，则该测试点得分比例为：

$$\min\left(1.0,\sqrt{\frac{2N\lceil \log_2 N \rceil}{Q}}\right)$$

样例说明

原题在此处给出了一张隐藏树示意图，并展示了与评测系统的一组交互过程。
整理为 Hydro 题面时，请在此处补入原图。

对于这棵示例树，可能的一组交互如下：

选手	评测系统
solve(5)
query({1, 5}, 2)	false
query({2, 4}, 5)	true
query({2, 4, 5}, 5)
query({2, 4, 5}, 3)	false
answer(1, 5)
answer(2, 5)
answer(5, 4)
answer(1, 3)

说明

这是一道提交函数题。提交时：

• 不要自己编写 main 函数；
• 不要直接读写标准输入输出；
• 只需按要求实现 solve(int n)。