#include "tree.h"
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
typedef vector <int> Vec;
random_device rd;
mt19937 Rng(time(0));
const int maxn = 2005, INF = 1e9 + 7;
int n, Root, Dep[maxn], D[maxn][maxn], Dist[maxn];
Vec Floor[maxn], G[maxn];
int ask(int u, vector<int> v);
void answer(int u, int v);
inline int Rand(int l, int r) { return Rng() % (r - l + 1) + l; }
inline void Add(int u, int v) {
    G[u].emplace_back(v), G[v].emplace_back(u);
    answer(u, v);
}
// inline void Random_Shuffle(Vec &A, Vec &Point, Vec &Cnt, int Siz) {
//     for(register int i = 1; i < Cnt.size(); ++i) swap(Cnt[i], Cnt[Rng() % i]);
//     Siz = max(1, Rand(A.size() / 3, A.size() * 7 / 12));
//     for(register int i = 0; i < Siz; ++i) Cnt.emplace_back(A[i]);
// }
inline int Dis_Sum(int x, Vec S) {
    int Sum = 0;
    for(int i : S) Sum += D[x][i];
    return Sum;
}
inline void Search(int *Dis, int S) {
    fill(Dis + 1, Dis + n + 1, INF);
    Dis[S] = 0;
    queue <int> Q;
    while(!Q.empty()) {
        int x = Q.front(); Q.pop();
        for(int y : G[x])
            if(Dis[y] > Dis[x] + 1) {
                Dis[y] = Dis[x] + 1;
                Q.emplace(y);
            }
    }
}
inline bool cmp(int x, int y) { return Dist[x] < Dist[y]; }
inline void Solve(Vec A, Vec B) {
    if(A.empty() || B.empty()) return ;
    if(A.size() == 1) {
        for(int i : B) Add(A[0], i);
        return ;
    }
    if(B.size() == 1) {
        for(int i : A)
            if(ask(i, B) == 1) { Add(i, B[0]); break; }
        return ;
    }
    Vec Point, Cnt = A; int Siz;
//    Random_Shuffle(A, Point, Cnt, Siz);
    for(register int i = 1; i < Cnt.size(); ++i) swap(Cnt[i], Cnt[Rng() % i]);
    Siz = max(1, Rand(A.size() / 3, A.size() * 7 / 12));
    for(register int i = 0; i < Siz; ++i) Point.emplace_back(Cnt[i]);
    for(int i : A) Dist[i] = Dis_Sum(i, Point);
    for(int i : B) Dist[i] = ask(i, Point);
    sort(A.begin(), A.end(), cmp);
    sort(B.begin(), B.end(), cmp);
    vector < Vec > VecA, VecB;
    int LA = 0, RA, LB = 0, RB = -1;
    while(LA < A.size()) {
        RA = LA;
        while(RA + 1 < A.size() && Dist[A[RA + 1]] == Dist[A[LA]]) ++RA;
        while(LB < B.size() && Dist[B[LB]] <  Dist[A[LA]] + Point.size()) ++LB;
        while(RB + 1 < B.size() && Dist[B[RB + 1]] <= Dist[A[LA]] + Point.size()) ++RB;
        if(LB <= RB) {
            Vec CntA, CntB;
            for(register int i = LA; i <= RA; ++i) CntA.emplace_back(A[i]);
            for(register int i = LB; i <= RB; ++i) CntB.emplace_back(B[i]);
            VecA.emplace_back(CntA), VecB.emplace_back(CntB);
        }
    }
    for(register int i = 0; i < VecA.size(); ++i) Solve(VecA[i], VecB[i]);
}
void solver(int _n, int A, int B) {
    n = _n;
    Root = Rand(1, n);
    for(register int i = 1; i <= n; ++i) Dep[i] = ask(i, Vec(1, Root));
    for(register int i = 1; i <= n; ++i) Floor[Dep[i]].emplace_back(i);
    for(register int i = 0; i <= n; ++i) {
        if(Floor[i].size() && Floor[i + 1].size()) Solve(Floor[i], Floor[i + 1]);
        for(int j : Floor[i + 1]) Search(D[j], j); 
    }
}