#include "tree.h"
#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


mt19937 rnd(234234);
const ll inf = 1e18;

#ifdef LOCAL
bool local = true;
#else
bool local = false;
#endif


void solve_aboba(vector<int> &a, int rt = -1, vector<int> dsts = {}){
    int n = a.size();
    if(n <= 1){
        return;
    }
    if(n == 2){
        answer(a[0], a[1]);
        return;
    }
    int u, v;
    int dst;
    if(rt == -1){
        auto gen_uv = [&](){
            int u = a[rnd() % n];
            int v = a[rnd() % n];
            while(u == v){
                v = a[rnd() % n];
            }
            return make_pair(ask(u, {v}), make_pair(u, v));
        };
        auto gd_uv = gen_uv();
        if(n >= 25){
            for(int itr = 0; itr < 6; itr += 1){
                gd_uv = max(gd_uv, gen_uv());
            }
        }
        dst = gd_uv.first;
        auto uv = gd_uv.second;
        u = uv.first;
        v = uv.second;
    } else{
        u = rt;
        auto gdv = make_pair(-1, -1);
        for(int i = 0; i < n; i += 1){
            gdv = max(gdv, make_pair(dsts[i], a[i]));
        }
        dst = gdv.first;
        v = gdv.second;
        if(dst == 1){
            for(auto v: a){
                if(v != rt){
                    answer(rt, v);
                }
            }
            return;
        }
    }
    vector<vector<int>> vrtcs(dst + 1);
    vector<vector<int>> vdsts(dst + 1);
    vrtcs[0].push_back(u);
    vdsts[0].push_back(0);
    vrtcs[dst].push_back(v);
    vdsts[dst].push_back(0);
    vector<int> base_vrtcs(dst + 1);
    base_vrtcs[0] = u;
    base_vrtcs[dst] = v;
    for(int i = 0; i < n; i += 1){
        if(a[i] == u || a[i] == v){
            continue;
        }
        int x = a[i];
        int dstu;
        if(rt == -1){
            dstu = ask(u, {x});
        } else{
            dstu = dsts[i];
        }
        int dstv = ask(v, {x});
        ll dst_bbr = (dstu + dstv - dst) / 2;
        ll rdstu = dstu - dst_bbr;
        vrtcs[rdstu].push_back(x);
        vdsts[rdstu].push_back(dst_bbr);
        if(dst_bbr == 0){
            base_vrtcs[rdstu] = x;
        }
    }
    for(int i = 0; i < dst; i += 1){
        answer(base_vrtcs[i], base_vrtcs[i + 1]);
    }
    for(int i = 0; i <= dst; i += 1){
        solve_aboba(vrtcs[i], base_vrtcs[i], vdsts[i]);
    }
}


int find_nxt(int v, vector<pair<int, int>> vrtcs, int d, vector<int> &a, bool cool = true){
    int n = vrtcs.size();
    if(vrtcs.size() == 1){
        return vrtcs[0].first;
    }
    int sm_sz = 0;
    for(auto x: vrtcs){
        sm_sz += x.second;
    }
    int f = sm_sz / 2;

    vector<pair<int, int>> vl;
    int sm_l = 0;
    for(int i = 0; i < n; i += 1){
        auto x = vrtcs[i];
        if(cool){
            if(sm_l + x.second < f){
                vl.push_back(x);
                sm_l += x.second;
            } else{
                x.second = f - sm_l;
                vl.push_back(x);
                break;
            }
        } else{
            if(i < n / 2){
                vl.push_back(x);
            } else{
                break;
            }
        }
    }
    int m = (int)vl.size();
    vector<pair<int, int>> vr(vrtcs.begin() + m, vrtcs.end());
    vector<int> avl, avr;
    for(auto x: vl){
        avl.push_back(a[x.first]);
    }
    for(auto x: vr){
        avr.push_back(a[x.second]);
    }
    int rs = -1;
    if(ask(a[v], avl) == (d + 2) * m){
        rs = find_nxt(v, vr, d, a);
    } else{
        rs = find_nxt(v, vl, d, a);
    }
    return rs;
}


void solve_fuck(vector<int> a){
    int n = a.size();
    int u = rnd() % n;
    vector<vector<int>> f(n);
    f[0].push_back(u);
    vector<int> dsts(n);
    dsts[u] = 0;
    for(int v = 0; v < n; v += 1){
        if(u == v){
            continue;
        }
        int d = ask(a[u], {a[v]});
        f[d].push_back(v);
        dsts[v] = d;
    }
    vector<vector<int>> t(n);
    vector<int> sz(n, 0);
    vector<int> par(n, -1);
    for(int md = 1; md < n; md += 1){
        if(f[md].empty()){
            break;
        }
        sz.assign(n, 0);
        for(auto v: f[md - 1]){
            int bbr = v;
            while(bbr != -1){
                sz[bbr] += 1;
                bbr = par[bbr];
            }
        }
        for(auto v: f[md]){
            int prnt = u;
            if(md > 1){
                int q = u;
                vector<int> usd(n, 0);
                while(dsts[q] < md - 1){
                    if(sz[q] == 1){
                        while(dsts[q] < md - 1){
                            int nxt = -1;
                            for(auto to: t[q]){
                                if(!usd[to] && sz[to] > 0){
                                    nxt = to;
                                }
                            }
                            q = nxt;
                        }
                        break;
                    }
                    if(!usd[q]){
                        int z = q;
                        vector<int> way = {z};
                        usd[z] = true;
                        while(!t[z].empty() && dsts[z] < md - 1){
                            pair<int, int> nxt = {-1, -1};
                            for(auto to: t[z]){
                                if(!usd[to]){
                                    nxt = max(nxt, make_pair(sz[to], to));
                                }
                            }
                            if(nxt.first == -1){
                                break;
                            }
                            z = nxt.second;
                            way.push_back(z);
                            usd[z] = true;
                        }
                        int dstz = ask(a[v], {a[z]});
                        int dstlca = (dsts[z] + dsts[v] - dstz) / 2;
                        q = way[dstlca - dsts[q]];
                    } else{
                        vector<pair<int, int>> vrtcs;
                        for(auto to: t[q]){
                            if(!usd[to] && sz[to] > 0){
                                vrtcs.push_back(make_pair(to, sz[to]));
                            }
                        }
                        // shuffle(all(vrtcs), rnd);
                        q = find_nxt(v, vrtcs, md - dsts[q] - 1, a, false);
                    }
                }
                prnt = q;
            }
            t[prnt].push_back(v);
            par[v] = prnt;
            answer(a[v], a[prnt]);
        }
    }
}


void solver(int n, int A, int B){
    vector<int> a(n);
    for(int i = 0; i < n; i += 1){
        a[i] = i + 1;
    }
    solve_fuck(a);
}


/*

7 1000 1000
1 2
2 3
1 4
1 5
5 6
4 7

*/