考虑让选取的集合更加特殊，不妨就让 \(S = \{x\}\)。
那么这个时候能发现询问 \((S = \{x\}, T, v)\) 得到的就是以 \(x\) 为根时 \(v\) 的子树内 \(T\) 中的点的数量。
考虑定个根，不妨为 \(1\)，同时令 \(S = \{1\}\)。
那么询问 \((\{1\}, \{1, \cdots n\} \backslash \{1, x\}, x)\)，就可以得到 \(sz_x\)。
因为只有 \(sz_v < sz_u\) 的 \(v\) 可能是 \(u\) 的儿子，考虑按 \(sz\) 增序排序。
考虑当前处理到以 \(u\) 为父亲，寻找 \(u\) 的儿子。
令前面还没有确定父亲的点的集合叫做 \(P\)，那么询问 \((\{1\}, P, u)\), 就得到了 \(u\) 的儿子的数量。
对于找儿子，就可以考虑二分，询问 \((\{1\}, P_{1\sim i}, u)\)，找到最靠前的一个 \(i\)，然后删掉 \(P_i\) 继续找其他的儿子。
询问次数上界为 \(2n + \mathcal{O}(n\log n)\)。
代码
#include<bits/stdc++.h>
const int maxn = 5e2 + 10;
std::pair<int, int> p[maxn];
int ask(int x, int y, std::vector<int> &S) {
if (S.empty()) return 0;
std::cout << 1 << std::endl << x << std::endl << S.size() << std::endl;
for (int u : S) std::cout << u << ' ';
std::cout << std::endl << y << std::endl;
std::cin >> x;
return x;
}
int main() {
int n;
scanf("%d", &n);
std::vector<int> S;
p[1] = {n, 1};
for (int i = 2; i <= n; i++) S.push_back(i);
for (int i = 2; i <= n; i++) {
S.erase(std::find(S.begin(), S.end(), i));
p[i] = {ask(1, i, S), i};
S.push_back(i);
}
std::sort(p + 1, p + n + 1);
S.clear(), S.push_back(p[1].second);
std::vector<std::pair<int, int> > E;
for (int i = 2; i < n; i++) {
int cnt = ask(1, p[i].second, S);
while (cnt--) {
int l = 0, r = S.size() - 1, w;
while (l <= r) {
int mid = (l + r) >> 1;
std::vector<int> T(S.begin(), S.begin() + mid + 1);
ask(1, p[i].second, T) ? (w = mid, r = mid - 1) : (l = mid + 1);
}
E.emplace_back(p[i].second, S[w]), S.erase(S.begin() + w);
}
S.push_back(p[i].second);
}
for (int x : S) E.emplace_back(1, x);
std::cout << "ANSWER" << std::endl;
for (auto _ : E) std::cout << _.first << ' ' << _.second << std::endl;
return 0;
}