这是一道交互题。
交互库里有一棵 $n$ 个点的树，你可以通过做若干次如下询问来确定这棵树：
给定一个节点集合 $S$ 和节点 $x$，交互库会告诉你 $x$ 是否在包含 $S$ 的最小连通块中。
Details
具体的，你需要引用头文件 D.h 并且实现以下函数：
std::vector<std::pair<int,int> > work(int n)这个函数接受一个节点数 $n$，返回一个 std::vector<std::pair<int,int> >，其中每个 std::pair<int, int> 都表示边的两个端点，且 vector 的长度恰好为 $n-1$。
你可以调用以下函数：
bool ask(std::vector<int> S, int x)用途见题目描述。
Custom Test
下发文件包含 D.h 以及交互库的实现 implementer.cpp，评测程序示例将读入如下格式的输入数据：
第一行包括一个正整数 $n$。
接下来 $n-1$ 行，每行两个正整数 $x,y$，表示一条边的两个端点。下标从 $1$ 开始。
Constraints
对于所有数据，$n \le 1000$。并且设你在某个测试点中做了 $Q$ 次询问，则将获得 $\min\left\{\left\lfloor\dfrac{2.2\times10^6}{Q}\right\rfloor,100\right\}$ 分，总的得分是所有测试点得分的最小值。
注意：由于交互库处理询问的复杂度为 $O(|S|)$，因此你需要注意 $\sum |S|$ 的大小可能会引起超时。
$\text{subtask1(23pts)}:n=998$ 且树是一条链。
$\text{subtask2(33pts)}:n=999$ 且树上每个点 $i$ 的父亲在 $1,2,\cdots,i-1$ 中均匀随机。
$\text{subtask3(44pts)}:n=1000$，无特殊限制。
无根树不好做，先定一个根1.
通过询问，我们可以很轻松的判断出一个点是否为另一个点的祖先。
定义一个函数 \(f(x)\) 为把 \(x\) 的子树给建好
现在我们可以把所有 \(x\) 子树内的点都给递归解决掉，然后他的后代中所有没有父亲的父亲一定是 \(x\) 点。
问题来了，如何迅速找到一个在 \(x\) 子树中的点呢？我们可以二分，每次把二分到的点放入集合，然后再把1塞进去，询问 \(x\) 是否在其中就可以了。
而如何找到 \(x\) 子树中没连父亲的点也可以用同样的方法。那么就做完了。
略微卡常，可以卡的点包括：直接二分而不用整体二分会更少次数，每次询问二分前先判断一次整个区间是否存在这样的点。
#include"C.hpp"
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int p,q,n,st[N],nw[N],fa[N];
vector<pair<int,int> >ans;
vector<int>ak;
void del(int a[],int&n,int x)
{
for(int i=1;i<=n;i++)
if(a[i]==x)
for(int j=i;j<n;j++)
a[j]=a[j+1];
--n;
}
void solve(int x)
{
del(nw,p,x);
while(1)
{
// puts("NO!!!");
int l=1,r=p;
ak.clear();
for(int i=l;i<=r;i++)
ak.push_back(nw[i]);
ak.push_back(1);
if(!ask(ak,x))
break;
while(l<r)
{
int md=l+r>>1;
ak.clear();
for(int i=l;i<=md;i++)
ak.push_back(nw[i]);
ak.push_back(1);
if(ask(ak,x))
r=md;
else
l=md+1;
}
if(l>p)
break;
// ak.clear();
// ak.push_back(1);
// ak.push_back(nw[l]);
// if(!ask(ak,x))
// break;
solve(nw[l]);
}
while(1)
{
// puts("NO!!!");
int l=1,r=q;
ak.clear();
for(int i=l;i<=r;i++)
if(st[i]^x)
ak.push_back(st[i]);
ak.push_back(1);
if(!ask(ak,x))
break;
while(l<r)
{
int md=l+r>>1;
ak.clear();
for(int i=l;i<=md;i++)
if(st[i]^x)
ak.push_back(st[i]);
ak.push_back(1);
if(ask(ak,x))
r=md;
else
l=md+1;
}
if(l>q||st[l]==x)
break;
// ak.clear();
// ak.push_back(1);
// if(st[l]^x)
// ak.push_back(st[l]);
// if(!ask(ak,x))
// break;
fa[st[l]]=x;
ans.push_back(make_pair(st[l],x));
del(st,q,st[l]);
}
}
vector<pair<int,int> >work(int n){
::n=p=n;
q=n-1;
for(int i=1;i<=n;i++)
st[i-1]=nw[i]=i;
solve(1);
return ans;
}