#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_>=V_##_END; V_--)
#ifdef _WIN32
#define long int64_t
#endif
#define _UN using namespace
using namespace std;
int ask(int u, vector<int> S);
void answer(int u, int v);
const int MAXN=1010;
mt19937 rng;
vector<int> vec[MAXN];
int fa[MAXN],up[MAXN][11],dep[MAXN];
void upd(int u,int fa_){
    up[u][0]=fa[u]=fa_,dep[u]=dep[fa_]+1;
    RNG(i,1,10) up[u][i]=up[up[u][i-1]][i-1];
}
int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    int d=dep[u]-dep[v];
    IRNG(i,10,0){
        if((d>>i)&1) u=up[u][i];
    }
    if(u==v) return u;
    IRNG(i,10,0){
        if(up[u][i]!=up[v][i]) u=up[u][i],v=up[v][i];
    }
    return fa[u];
}
int dist(int u,int v){ return dep[u]+dep[v]-2*dep[lca(u,v)]; }
int F[MAXN],G[MAXN];
void calc(vector<int>& A,vector<int>& B){
    if(A.empty()){ assert(B.empty()); return; }
    if(B.empty()) return;
    if(A.size()==1){
        for(int u:B) answer(A[0],u),upd(u,A[0]);
        return;
    }
    shuffle(A.begin(),A.end(),rng());
    vector<int> Al(A.begin(),A.begin()+A.size()/2);
    map<int,vector<pair<int,int>>> mp;
    for(int u:A){
        F[u]=0;
        for(int v:Al) F[u]+=dist(u,v);
        mp[F[u]].push_back({u,1});
    }
    for(int u:B) G[u]=ask(u,Al)-int(Al.size()),mp[G[u]].push_back({u,2});
    for(const auto& [_,vc]:mp){
        vector<int> A1,B1;
        for(auto [u,tp]:vc) (tp==1?A1:B1).push_back(u);
        calc(A1,B1);
    }
}
void solver(int n,int,int){
    int rt=int(rng()%n+1);
    vec[0]={rt};
    RNG(u,1,n){
        if(u!=rt) vec[ask(u,{rt})].push_back(u);
    }
    RNG(i,0,n-1) calc(vec[i],vec[i+1]);
}
#if defined(_LOCAL_)
#if 0
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
//  freopen("out","w",stdout);
//  freopen("/dev/null","w",stderr);
#else
//  freopen("swap.in","r",stdin);
//  freopen("swap.out","w",stdout);
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
}
#endif
#include "grader.cpp"
#else
#include "tree.h"
#endif

implementer.cpp: In function ‘void regduj260135279::init()’:
implementer.cpp:32:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   32 |                 scanf("%d",&n);
      |                 ~~~~~^~~~~~~~~
implementer.cpp:45:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   45 |                         scanf("%d%d",&u,&v);
      |                         ~~~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:4:
/usr/include/c++/13/bits/stl_algo.h: In instantiation of ‘void std::shuffle(_RAIter, _RAIter, _UGenerator&&) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >; _UGenerator = long unsigned int]’:
answer.code:44:12:   required from here
/usr/include/c++/13/bits/stl_algo.h:3763:9: error: ‘std::remove_reference<long unsigned int>::type’ {aka ‘long unsigned int’} is not a class, struct, or union type
 3763 |         __uc_type;
      |         ^~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:3791:44: error: ‘std::remove_reference<long unsigned int>::type’ {aka ‘long unsigned int’} is not a class, struct, or union type
 3791 |           const pair<__uc_type, __uc_type> __pospos =
      |                                            ^~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:3791:44: error: ‘std::remove_reference<long unsigned int>::type’ {aka ‘long unsigned int’} is not a class, struct, or union type