#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
using ll=long long;
mt19937 eng(random_device{}());
template<typename T>
T rand(const T &_l,const T &_r){
	return uniform_int_distribution<T>(_l,_r)(eng);
}
const int N=1005;
int rt,dep[N],dis[N][N];
vector<int> poi[N],e[N];
void link(int u,int v){
	e[u].push_back(v);
	e[v].push_back(u);
	answer(u,v);
}
void get_dis(int u,int fa,int rt){
	if(u!=rt){
		dis[rt][u]=dis[rt][fa]+1;
	}
	for(int v:e[u]){
		if(v!=fa){
			get_dis(v,u,rt);
		}
	}
}
int my_ask(int u,vector<int> vec){
	int ans=0;
	for(int v:vec) ans+=dis[u][v];
	return ans;
}
void solver(int n,[[maybe_unused]] int A,[[maybe_unused]] int B){
	rt=rand(1,n);
	For(i,1,n){
		if(i!=rt){
			dep[i]=ask(i,{rt});
			poi[dep[i]].push_back(i);
		}
	}
	for(int u:poi[1]) link(rt,u);
	For(d,2,n){
		for(int u:poi[d]){
			For(i,1,n) get_dis(i,0,i);
			vector<int> may(poi[d-1]);
			while(may.size()>1){
				shuffle(range(may),eng);
				vector<int> cur(may.begin(),may.begin()+may.size()/2+1);
				int ans=ask(u,cur);
				vector<int> nmay;
				for(int v:may){
					if(my_ask(v,cur)+int(cur.size())==ans){
						nmay.push_back(v);
					}
				}
				may=nmay;
			}
			link(may[0],u);
		}
	}
}
#ifdef zyz
#include "grader.cpp"
#endif