#include<bits/stdc++.h>
#include<random>
#include "tree.h"
int ask(int u,std::vector<int>v);
void answer(int u,int v);
const int N=1010;
std::mt19937 rnd(1);
int d[N];
inline void Shuffle(std::vector<int> &x){for(int i=0;i<int(x.size());++i) std::swap(x[i],x[rnd()%int(x.size())]);}
inline int randint(int l,int r){return l+rnd()%(r-l+1);}
std::map<std::pair<int,int>,int> mp;
inline int Query(int x,std::vector<int> &y)
{
	std::vector<std::pair<int,int> > tmp;
	for(auto c:y) tmp.push_back(std::make_pair(std::min(x,c),std::max(x,c)));
	int cnt=0,ans=0;
	std::vector<int> v;
	for(auto c:tmp) cnt+=int(mp.count(c))^1;
	if(!cnt)
	{
		for(auto c:tmp) ans+=mp[c];
		return ans;
	}
	else if(cnt==1)
	{
		for(auto c:tmp)
			if(mp.count(c)) ans+=mp[c];
			else v.push_back(c.first^c.second^x),ans+=mp[c]=ask(x,v);
		return ans;
	}
	else
	{
		for(auto c:tmp)
			if(mp.count(c)) ans+=mp[c];
			else v.push_back(c.first^c.second^x);
		return ans+ask(x,v);
	}
}
void dfs(std::vector<int> A,std::vector<int> B)
{
	if(A.empty()||B.empty()) return ;
	if(int(A.size())==1)
	{
		for(auto x:B) answer(A[0],x);
		return ;
	}
	const int SZ=22;
	if(int(A.size())==2&&int(B.size())>=SZ)
	{
		std::vector<int> tmp;
		std::vector<bool> b;
		tmp.push_back(A[1]);
		int D=Query(A[0],tmp);
		b.resize(B.size());
		for(int i=0;i<int(B.size());++i) b[i]=false;
		for(int i=0;i+SZ<int(B.size());i+=SZ)
		{
			tmp.clear();
			for(int j=i;j<i+SZ;++j) tmp.emplace_back(B[j]);
			int cur=Query(A[0],tmp);
			if(cur==SZ)
				for(int j=i;j<i+SZ;++j) answer(A[0],B[j]),b[j]=true;
			else if(cur==(D+1)*SZ)
				for(int j=i;j<i+SZ;++j) answer(A[1],B[j]),b[j]=true;
		}
		tmp.clear();
		for(int i=0;i<int(B.size());++i) if(!b[i]) tmp.emplace_back(B[i]);
		B=tmp;
		if(B.empty()) return ;
	}
	Shuffle(A);
	std::vector<int> q;
	int c=randint(0.4*A.size(),0.6*A.size())+1;
	if(c>int(A.size())) c=A.size()-1;
	for(int i=0;i<int(A.size())/2;++i) q.emplace_back(A[i]);
	std::unordered_map<int,std::vector<int> > mp1,mp2;
	for(auto x:A) mp1[Query(x,q)].emplace_back(x);
	for(auto x:B) mp2[Query(x,q)].emplace_back(x);
	for(auto x:mp1)
	{
		std::vector<int> nxt1,nxt2;
		for(auto y:x.second) nxt1.emplace_back(y);
		if(mp2.count(x.first+int(q.size()))) for(auto y:mp2[x.first+int(q.size())]) nxt2.emplace_back(y);
		dfs(nxt1,nxt2);
	}
}
int R;
namespace TEST
{
	using namespace std;
	#define macro_expand(x) #x
	#define print_macro(x) printf("%s\n",macro_expand(x))
	#define FOR(i,l,r) for(int i=(l),i##ADJK=(r);i<=i##ADJK;++i)
	#define ROF(i,r,l) for(int i=(r),i##ADJK=(l);i>=i##ADJK;--i)
	const int MN=1e3+5;
	int N,wes[MN],siz[MN],dep[MN];
	vector<int> son[MN];
	bool tag[MN],t2[MN];
	void dfs(int u,int ff){
		siz[u]=1;
		for(int v:son[u]){
			dfs(v,u);
			siz[u]+=siz[v];
			if((!wes[u])||siz[v]>siz[wes[u]])wes[u]=v;
		}
		for(int v:son[u]){
			if(v!=wes[u])tag[u]|=t2[v];
			t2[u]|=t2[v];
		}
	}
	int jg(int u,vector<int> s){
		int ret=0;
		ret+=dep[u]*((int)s.size());
		for(int v:s)ret+=dep[v];
		return (ret-ask(u,s))/2;
	}
	int get(vector<int> s,int u){ // 可以试图加个随机化减小常数？
		if(s.size()==1)return s[0];
		vector<int> ls,rs;
		FOR(i,1,s.size()/2)ls.push_back(s[i-1]);
		FOR(i,s.size()/2+1,s.size())rs.push_back(s[i-1]);
		int t=ask(u,ls);
		if(t<((int)ls.size())*(dep[u]-dep[ls[0]]+2))return get(ls,u);
		// 注意这里不是什么 dep[ls[0]]+2 是 dep[u]-dep[ls[0]]+2
		else return get(rs,u);
	}
	int calc(int l,int r){return (l+r)*(r-l+1)/2;}
	bool debug=0;
	int find(int u,int nr){ // u 是要找的，nr 是当前的根
		// if(debug)cerr<<"u:"<<u<<" nr:"<<nr<<endl;
		if(dep[nr]==dep[u]-1)return nr;
		vector<int> chain,pre;
		int now=nr;
		while(now){
			// 注意，t2[now] && (!wes[now]) 也可能成为答案
			if(tag[now]||((!wes[now])&&t2[now]))chain.push_back(now);
			now=wes[now];
		}
		pre.resize(chain.size());
		assert(chain.size()>=1);
		pre[0]=dep[chain[0]];
		FOR(i,1,chain.size()-1)pre[i]=pre[i-1]+dep[chain[i]];
		int l=0,r=(int)chain.size()-2,sz=chain.size()-1,p=chain.size()-1;
		if(chain.size()>1){
			int t=jg(u,chain);
			while(l<=r){
				int mid=(l+r)>>1;
				if((sz-mid+1)*dep[chain[mid]]+((mid-1>=0)?pre[mid-1]:0)>=t){
					p=mid;
					r=mid-1;
				}else l=mid+1;
			}
		}else p=0;
		vector<int> ls;
		for(int v:son[chain[p]])
			if(v!=wes[chain[p]]&&t2[v])ls.push_back(v);
		if(ls.size()==0)return chain[p];
		int nxt=get(ls,u);
		return find(u,nxt);
	}
	bool cmp(const int &x,const int &y){return dep[x]<dep[y];}
	void solver(int n,int A,int B)
	{
		// TODO: your solver
		N=n;
		int rt=R;
		static int ord[MN],fa[MN];
		FOR(i,1,N){
			if(i!=rt)
			{
//				dep[i]=ask(rt,vector<int>({i}))+1;
				dep[i]=d[i];
			}
			ord[i]=i;
		}
		dep[rt]=1;
		sort(ord+1,ord+N+1,cmp); // 记得排序
		int last=1;
		FOR(i,2,N){
			if(dep[ord[i]]!=dep[ord[i-1]]){
				FOR(j,1,N)tag[j]=t2[j]=0;
				FOR(j,last,i-1){ // 这个循环变量别重名……
					t2[ord[j]]=1;
					if(fa[ord[j]])
						son[fa[ord[j]]].push_back(ord[j]);
				}
				dfs(rt,0);
				last=i;
			}
			fa[ord[i]]=find(ord[i],rt);
		}
		FOR(i,1,N)if(fa[i])answer(i,fa[i]);
	}
}
void solver(int n,int A,int B)
{
	R=1+rnd()%n;
	std::vector<int> tmp;
	int mx=0;
	for(int i=1;i<=n;++i) tmp.clear(),tmp.emplace_back(R),d[i]=ask(i,tmp),mx=std::max(mx,d[i]);
	if(mx<=6){TEST::solver(n,A,B);return ;}
	for(int i=1;i<=n;++i) if(d[i]==1) answer(R,i);
	for(int i=1;i<n;++i)
	{
		std::vector<int> p,q;
		for(int j=1;j<=n;++j)
		{
			if(d[j]==i) p.emplace_back(j);
			else if(d[j]==i+1) q.emplace_back(j);
		}
		dfs(p,q);
	}
}