#include <bits/stdc++.h>
#include "passageconstruction.h"
#define pii pair<int,int>
#define s1 first
#define s2 second
#define N 50011
using namespace std;
struct edge{int v,id;};vector<edge> G[N];vector<int> vG[N],E[N];
int siz[N],Su,Sv,eid,mxh,n,a[N],eu[N],ev[N],mkD;bool vis[N];
int fa[N][21],dep[N];
void addedge(int f,int u)
{
	E[f].push_back(u);
	fa[u][0]=f;for(int i=1;i<=20;++i)fa[u][i]=fa[fa[u][i-1]][i-1];
}
void dfs0(int u,int f,int SIZ)
{
	siz[u]=(dep[a[u]]==mkD);
	for(auto [v,id]:G[u])if(v^f&&!vis[id])
	{
		dfs0(v,u,SIZ);siz[u]+=siz[v];
		if(mxh>max(SIZ-siz[v],siz[v]))mxh=max(SIZ-siz[v],siz[v]),Su=u,Sv=v,eid=id;
	}
}
void dfs1(int u,int f,vector<int> &V,int lst)
{
	if(a[u]!=lst){V.push_back(a[u]);return;}
	for(auto [v,id]:G[u])if(v^f&&!vis[id])dfs1(v,u,V,lst);
}
int dfstt(int u,int f)
{
	int ans=(dep[a[u]]==mkD);
	for(auto [v,id]:G[u])if(v^f&&!vis[id])ans+=dfstt(v,u);
	return ans;
}
int dd(int u,int f){if(dep[a[u]]==mkD)return u;int w=-1;for(auto [v,id]:G[u])if(v^f&&!vis[id])w&=dd(v,u);return w;}
void solve(int u,int SIZ,vector<int> nd)
{
	if(!SIZ||nd.empty())return;
	if(SIZ==1||nd.empty())
	{
		int tt=dd(u,0);
		for(int x:nd)addedge(a[tt],x);return;
	}
	mxh=1e9;
	dfs0(u,0,SIZ);
	vector<int> vu;
	vu.push_back(a[Sv]);dfs1(Su,Sv,vu,a[Sv]);
	int sizu=dfstt(Su,Sv),sizv=dfstt(Sv,Su);
	vis[eid]=1;
	vector<int> tou,tov;
	vector<int> ru;
	if(vu.size()==1)ru.resize(nd.size(),1);else ru=QueryLCA(nd,vu,a[Sv]);
	for(int i=0;i<nd.size();++i)
	{
		if(!ru[i])tou.push_back(nd[i]);
		else tov.push_back(nd[i]);
	}
	int tu=Su,tv=Sv;
	solve(tu,sizu,tou);solve(tv,sizv,tov);
}
int lca(int u,int v)
{
	if(!u||!v)return u^v;
	if(dep[u]<dep[v])swap(u,v);for(int i=20;~i;--i)if(dep[u]-(1<<i)>=dep[v])u=fa[u][i];if(u==v)return u;
	for(int i=20;~i;--i)if(fa[u][i]^fa[v][i])u=fa[u][i],v=fa[v][i];return fa[u][0];
}
vector<int> vd[N],vn;int dfn[N],rk[N],ndfn[N],nrk[N],en,sz,rt;
bool cmp(int a,int b){return dfn[a]<dfn[b];}
int buildvG(vector<int> v)
{
	sort(v.begin(),v.end(),cmp);
	for(int i=v.size()-1;i;--i)v.push_back(lca(v[i],v[i-1]));
	sort(v.begin(),v.end(),cmp);v.resize(unique(v.begin(),v.end())-v.begin());
	for(int i=1;i<v.size();++i)vG[lca(v[i],v[i-1])].push_back(v[i]);
	vn=v;
	return v[0];
}
int buildG(int u)
{
	if(vG[u].empty()){a[++sz]=u;return sz;}
	if(vG[u].size()==1)
	{
		int D=++sz,V=buildG(vG[u][0]);
		++en;
		G[D].push_back({V,en});G[V].push_back({D,en});
		a[D]=u;
		return D;
	}
	else
	{
		int lst=buildG(vG[u].back());
		for(int i=vG[u].size()-2;~i;--i)
		{
			int D=++sz,V=buildG(vG[u][i]);
			++en;
			G[D].push_back({lst,en});G[lst].push_back({D,en});
			++en;
			G[D].push_back({V,en});G[V].push_back({D,en});
			a[D]=u;lst=D;
		}
		return lst;
	}
}
int cn;
void proc(int d)
{
	for(int x:vn)vG[x].clear();vn.clear();
	for(int i=1;i<=sz;++i)G[i].clear(),vis[i]=0;sz=en=0;
	rt=buildvG(vd[d-1]);
	rt=buildG(rt);
	mkD=d-1;
	solve(1,sz,vd[d]);
	nrk[0]=0;
	for(int i=1;i<=cn;++i)
	{
		nrk[++nrk[0]]=rk[i];
		if(dep[rk[i]]==d-1)
		{
			for(int x:E[rk[i]])if(dep[x]==d)nrk[++nrk[0]]=x;
		}
	}
	for(int i=1;i<=nrk[0];++i)rk[i]=nrk[i];cn=nrk[0];
	for(int i=1;i<=cn;++i)dfn[rk[i]]=i;
}
vector<pii> res;
bool dfs_(int u,int f)
{
	vector<int> ch;
	for(int v:E[u])if(v^f&&dfs_(v,u))ch.push_back(v);
	if(ch.size()%2==0){for(int i=0;i<ch.size();i+=2)res.push_back({ch[i],ch[i+1]});return 1;}
	else{for(int i=1;i<ch.size();i+=2)res.push_back({ch[i],ch[i+1]});res.push_back({ch[0],u});return 0;}
}
vector<pii> ConstructPassages(int n,const vector<pii> &useless)
{
	::n=n;
	int mxd=0;
	for(int i=2;i<=2*n;++i)dep[i]=GetDistance(1,i),vd[dep[i]].push_back(i),mxd=max(mxd,dep[i]);
	vd[0].push_back(1);dfn[1]=rk[1]=cn=1;
	for(int i=1;i<=mxd;++i)proc(i);
	dfs_(1,0);
	return res;
}