#include <bits/stdc++.h>
#include "passageconstruction.h"
using namespace std;
int n,dep[10010],mdep,dfn[10010],tot,fa[14][10010],siz[20010];
int node_siz,edge_siz,id[10010],nowdep,vis[20010],msiz,eid,eU,eV;
vector<int>S[10010],e[10010],E[10010],lst;
vector< pair<int,int> >ans,se[20010];
inline void adde(int x,int y)
{
	e[x].emplace_back(y);
	fa[0][y]=x;
	for(int i=1;i<14;++i)fa[i][y]=fa[i-1][fa[i-1][y]];
	return ;
}
inline int get_lca(int x,int y)
{
	if(x==y)return x;
	if(dep[x]<dep[y])swap(x,y);
	for(int i=13;~i;--i)while(dep[fa[i][x]]>=dep[y])x=fa[i][x];
	if(x==y)return x;
	for(int i=13;~i;--i)while(fa[i][x]^fa[i][y])x=fa[i][x],y=fa[i][y];
	return fa[0][x];
}
inline void dfs(int rt)//求 dfs 序
{
	dfn[rt]=++tot;
	for(int i:e[rt])dfs(i);
	return ;
}
inline bool cmp(int x,int y){return dfn[x]<dfn[y];}
inline int build(vector<int>S)
{
	sort(S.begin(),S.end(),cmp);
	for(int i=(int)S.size()-1;i;--i)S.emplace_back(get_lca(S[i],S[i-1]));
	sort(S.begin(),S.end(),cmp);S.resize(unique(S.begin(),S.end())-S.begin());
	for(int i=1;i<(int)S.size();++i)E[get_lca(S[i],S[i-1])].emplace_back(S[i]);
	lst=S;
	return S[0];
}
inline int dfss(int rt,int da)// 三度化
{
	if(E[rt].empty())return id[++node_siz]=rt,node_siz;
	if(E[rt].size()==1)
	{
		int U=++node_siz,V=dfss(E[rt][0],rt);
		id[U]=rt;++edge_siz;
		se[U].emplace_back(make_pair(V,edge_siz));
		se[V].emplace_back(make_pair(U,edge_siz));
		return U;
	}
	else
	{
		int V=dfss(E[rt].back(),rt);
		for(int i=E[rt].size()-2;~i;--i)
		{
			int rot=++node_siz,U=dfss(E[rt][i],rt);
			++edge_siz;
			se[rot].emplace_back(make_pair(U,edge_siz));
			se[U].emplace_back(make_pair(rot,edge_siz));
			++edge_siz;
			se[rot].emplace_back(make_pair(V,edge_siz));
			se[V].emplace_back(make_pair(rot,edge_siz));
			V=rot;id[rot]=rt;
		}
		return V;
	}
	return 0;
}
inline int get_id(int rt,int da)
{
	if(dep[id[rt]]==nowdep)return id[rt];
	int an=0;
	for(pair<int,int>i:se[rt])
	{
		if(i.first==da||vis[i.second])continue;
		an|=get_id(i.first,rt);
	}
	return an;
}
inline void findroot(int rt,int da,int SZ)
{
	if(dep[id[rt]]==nowdep)siz[rt]=1;
	else siz[rt]=0;
	for(pair<int,int>i:se[rt])
	{
		if(i.first==da||vis[i.second])continue;
		findroot(i.first,rt,SZ);siz[rt]+=siz[i.first];
		if(msiz>max(siz[i.first],SZ-siz[i.first]))msiz=max(siz[i.first],SZ-siz[i.first]),eU=rt,eV=i.first,eid=i.second;
	}
	return ;
}
inline int dfssss(int rt,int da)// 求 siz
{
	int an=(dep[id[rt]]==nowdep);
	for(pair<int,int>i:se[rt])
	{
		if(i.first==da||vis[i.second])continue;
		an+=dfssss(i.first,rt);
	}
	return an;
}
inline void dfsssss(int rt,int da,vector<int>&S,int rot)// 求点集
{
	if(id[rt]^rot)return S.emplace_back(id[rt]),void();
	for(pair<int,int>i:se[rt])
	{
		if(i.first==da||vis[i.second])continue;
		dfsssss(i.first,rt,S,rot);
	}
	return ;
}
inline void dfz(int rt,int SZ,vector<int>nodeset)
{
	if(!SZ||nodeset.empty())return ;
	if(SZ==1)
	{
		int ID=get_id(rt,0);
		for(int i:nodeset)adde(ID,i);
		return ;
	}
	msiz=SZ+1;
	findroot(rt,0,SZ);
	vector<int>res,B,toU,toV;B.emplace_back(id[eU]);
	dfsssss(eV,eU,B,id[eU]);
	int sizU=dfssss(eU,eV),sizV=dfssss(eV,eU);
	vis[eid]=1;
	if(B.size()==1)res.resize(nodeset.size(),1);
	else res=QueryLCA(nodeset,B,id[eU]);
	for(int i=0;i<(int)nodeset.size();++i)
	{
		if(res[i])toU.emplace_back(nodeset[i]);
		else toV.emplace_back(nodeset[i]);
	}
	int eeU=eU,eeV=eV;
	dfz(eeU,sizU,toU);dfz(eeV,sizV,toV);
	return ;
}
inline void solve(int D)
{
	for(int i:lst)E[i].clear();
	for(int i=1;i<=node_siz;++i)se[i].clear();
	memset(vis,0,(edge_siz+1)<<2);
	node_siz=edge_siz=0;nowdep=D-1;
	int rot=build(S[D-1]);
	rot=dfss(rot,0);
	dfz(rot,node_siz,S[D]);
	tot=0;dfs(1);
	return ;
}
inline int dfsss(int rt)// 求匹配
{
	int son=0;
	for(int i:e[rt])
	{
		int p=dfsss(i);
		if(p)
		{
			if(son)
			{
				ans.emplace_back(make_pair(p,son));
				son=0;
			}
			else son=p;
		}
	}
	if(son)
	{
		ans.emplace_back(make_pair(rt,son));
		son=0;
	}
	else son=rt;
	return son;
}
vector< pair<int,int> >ConstructPassages(int N,const vector< pair<int,int> >&E)
{
	n=N;dep[0]=-1;
	for(int i=2;i<=(n<<1);++i)
	{
		S[dep[i]=GetDistance(1,i)].emplace_back(i);
		mdep=max(mdep,dep[i]);
	}
	S[0].emplace_back(1);dfn[1]=tot=1;
	for(int i=1;i<=mdep;++i)solve(i);
	dfsss(1);
	return ans;
}