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

using namespace std;

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

vector<vector<int>> ver;
vector<pair<int,int>> ans;
vector<int> baned,fa;

void dfs(int u,int dep=1,vector<int> brother=vector<int>()){
  vector<int> to;
  for(auto p:ver[dep]){
    if(fa[p]==u){
      to.emplace_back(p);
      continue;
    }
    if(baned[p]) continue;
    int dis=ask(u,vector<int>(1,p));
    if(dis==1){
      ans.emplace_back(make_pair(u,p));
      baned[p]=-1;
      fa[p]=u;
      to.emplace_back(p);
    }
    if(dis==3){
      int l=0, r=brother.size()-1;
      vector<int> tmp;
      int nxtmid=(l+r)>>1,lst=0;
      for(int i=0; i<=nxtmid; i++) tmp.emplace_back(brother[i]);
      while(l<r){
        auto T=ask(p,tmp);
        if(T==3*(nxtmid+1-lst)){
          l=nxtmid+1;
          lst=nxtmid;
          nxtmid=(l+r)>>1;
          tmp.clear();
          for(int i=l; i<=nxtmid; i++) tmp.emplace_back(brother[i]);
        }
        else{
          r=nxtmid;
          nxtmid=(l+r)>>1;
          while((int)tmp.size()>mid+1) tmp.pop_back();
        }
      }
      ans.emplace_back(make_pair(p,brother[l]));
      fa[p]=brother[l];
      baned[p]=1;
    }
  }
  shuffle(to.begin(),to.end(),gen);
  for(auto p:to){
    dfs(p,dep+1,to);
  }
}

void solver(int n,int A,int B){
  fa.resize(n+1),ver.resize(n+1); baned.resize(n+1);
  int root=gen()%n+1;
  for(int i=1; i<=n; i++){
    int x=ask(root,vector<int>(1,i));
    ver[x].emplace_back(i);
  }
  dfs(root);
  assert(ans.size()==(n-1)*1u);
  for(auto pt:ans){
    //cerr<<pt.first<<' '<<pt.second<<endl;
    answer(pt.first,pt.second);
  }
}

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);
      |                         ~~~~~^~~~~~~~~~~~~~
answer.code: In function ‘void dfs(int, int, std::vector<int>)’:
answer.code:44:33: error: ‘mid’ was not declared in this scope
   44 |           while((int)tmp.size()>mid+1) tmp.pop_back();
      |                                 ^~~