#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(36346346);
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<int> vrtcs, int d){
    int n = vrtcs.size();
    if(vrtcs.size() == 1){
        return vrtcs[0];
    }
    int m = (n / 2);
    vector<int> vl(vrtcs.begin(), vrtcs.begin() + m), vr(vrtcs.begin() + m, vrtcs.end());
    int rs = -1;
    if(ask(v, vl) == (d + 2) * m){
        rs = find_nxt(v, vr, d);
    } else{
        rs = find_nxt(v, vl, d);
    }
    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);
    sz[u] = 1;
    for(int md = 1; md < n; md += 1){
        if(f[md].empty()){
            break;
        }
        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(!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<int> vrtcs;
                        for(auto to: t[q]){
                            if(!usd[to]){
                                vrtcs.push_back(to);
                            }
                        }
                        q = find_nxt(v, vrtcs, md - dsts[q] - 1);
                    }
                }
                prnt = q;
            }
            t[prnt].push_back(v);
            par[v] = prnt;
            int bbr = v;
            while(bbr != -1){
                sz[bbr] += 1;
                bbr = par[bbr];
            }
            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

*/

answer.code:1:10: fatal error: tree.h: No such file or directory
    1 | #include "tree.h"
      |          ^~~~~~~~
compilation terminated.