#include "tree.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
vector<int> Dep[maxn], Edge[maxn], Cnt;
int Vst[maxn], a[maxn], Fa[maxn], flag[maxn];
int ask(int u, vector<int> v);
void answer(int u, int v);
inline void Search(int y, int d1, int x, int d2) {
    if(d2 == d1 - 1) { answer(x, y), Fa[y] = x, Edge[x].push_back(y); return ; }
    if(Edge[x].size() == 1) { Search(y, d1, Edge[x][0], d2 + 1); return ; }
    int tot = d1 - d2 - 1, l = 0, r = Edge[x].size() - 1, res = 0; Cnt.clear();
    while(l <= r) {
        int mid = (l + r) >> 1;
        Cnt.clear();
        for(register int i = l; i <= mid; ++i) Cnt.push_back(Edge[x][i]);
        int d = ask(y, Cnt);
        if(d < (tot + 2) * (mid - l + 1)) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    Search(y, d1, Edge[x][r], d2 + 1);
}
inline void Work(int n) {
    for(register int i = 1; i < n; ++i) {
        if(!Dep[i].size()) break;
        if(!Dep[i + 1].size()) break;
        int v = rand() % Dep[i].size(), u = Dep[i][v];
        for(register int i = 1; i <= n; ++i) Edge[i].clear(), flag[i] = 0;
        a[0] = u, flag[u] = 1;
        for(register int i = 1; a[i - 1]; ++i) a[i] = Fa[a[i - 1]], flag[a[i]] = 1;
        for(int y : Dep[i + 1]) {
            int d1 = ask(u, {y});
            if(d1 == 1) answer(u, y), Vst[y] = 1, Fa[y] = u;
            else Edge[a[d1 - 1 >> 1]].push_back(y);
        }
        for(int x : Dep[i]) {
            for(register int f = x; f; f = Fa[f]) {
                for(int y : Edge[f])
                    if(!Vst[y] && ask(x, {y}) == 1) answer(x, y), Vst[y] = 1, Fa[y] = x;
                    if (flag[f]) break;
            }
        }
    }
}
void solver(int n, int A, int B) {
    srand(time(0));
    int Root = rand() % n + 1, maxx = 0;
    for(register int i = 1; i <= n; ++i)
        if(Root != i) {
            int d1 = ask(Root, {i});
            maxx = max(maxx, d1);
            Dep[d1].push_back(i);
        }
    for(int i : Dep[1]) answer(Root, i), Fa[i] = Root, Edge[Root].push_back(i);
    if(maxx * maxx <= 4 * n) {
        for(register int i = 2; i < n; ++i) {
            if(!Dep[i].size()) break;
            for(int y : Dep[i]) Search(y, i, Root, 0);
        }
    } 
    else Work(n);
}