#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<random>
#include"passageconstruction.h"
#define SN 10000
using namespace std;
mt19937 RAND(random_device{}());
const int inf=(int)(1e9);
int n,rt,smz,minn,minn2,dfn[SN+1],sz[SN+1],leng,ps[SN+1],depth[SN+1];
bool used[SN+1],vis[SN+1],vst[SN+1];
vector<int>E[SN+1];
vector<int>ES[SN+1];
vector<int>sp[SN+1];
vector<int>p[SN+1];
vector<int>tans;
vector<pair<int,int> >ans;
void add_edge(int x,int y)
{
	ES[x].push_back(y),ES[y].push_back(x);
	return;
}
void dfs(int x)
{
	for (int i=0;i<E[x].size();++i)
	{
		dfs(E[x][i]);
		if (ps[x]&&ps[E[x][i]]) ans.push_back(make_pair(ps[x],ps[E[x][i]])),ps[x]=0;
		else ps[x]^=ps[E[x][i]];
	}
	if (ps[x]) ans.push_back(make_pair(ps[x],x)),ps[x]=0;
	else ps[x]=x;
	return;
}
void dfs2(int x)
{
	vector<int>st;
	int res=vis[x];
	sz[x]=vis[x],shuffle(E[x].begin(),E[x].end(),RAND);
	for (int i=0;i<E[x].size();++i)
	{
		dfs2(E[x][i]),sz[x]+=sz[E[x][i]],st.push_back(E[x][i]);
		if (sz[x]>1&&(max(sz[x],smz-sz[x])<minn||(max(sz[x],smz-sz[x])==minn&&sz[x]<minn2))) rt=x,minn=max(sz[x],smz-sz[x]),minn2=sz[x],tans=st;
	}
	st.clear();
	for (int i=E[x].size()-1;i>=0;--i)
	{
		st.push_back(E[x][i]),res+=sz[E[x][i]];
		if (res>1&&(max(res,smz-res)<minn||(max(res,smz-res)==minn&&res<minn2))) rt=x,minn=max(res,smz-res),minn2=res,tans=st;
	}
	return;
}
void dfs3(int x)
{
	if (vis[x]) vst[x]=1;
	for (int i=0;i<E[x].size();++i) dfs3(E[x][i]);
	return;
}
void solve(vector<int>A,vector<int>B)
{
	if (B.empty()) return;
	if (A.size()==1)
	{
		for (int i=0;i<B.size();++i) E[A[0]].push_back(B[i]);
		return;
	}
	if (A.size()==2)
	{
		vector<int>v=QueryLCA(B,{A[0],A[1]},A[0]);
		for (int i=0;i<B.size();++i)
		{
			if (v[i]) E[A[0]].push_back(B[i]);
			else E[A[1]].push_back(B[i]);
		}
		return;
	}
	minn=minn2=inf,rt=0,tans.clear();
	for (int i=0;i<A.size();++i) vis[A[i]]=1;
	smz=A.size(),dfs2(1);
	vector<int>v1;
	vector<int>v2;
	vector<int>s1;
	vector<int>s2;
	for (int i=0;i<tans.size();++i) dfs3(tans[i]);
	for (int i=0;i<A.size();++i)
	{
		if (vst[A[i]]) v1.push_back(A[i]);
		else v2.push_back(A[i]);
	}
	for (int i=0;i<A.size();++i) vis[A[i]]=vst[A[i]]=0;
	vector<int>v=QueryLCA(B,v1,rt);
	for (int i=0;i<v.size();++i)
	{
		if (!v[i]) s1.push_back(B[i]);
		else s2.push_back(B[i]);
	}
	solve(v1,s1),solve(v2,s2);
	return;
}
std::vector<std::pair<int,int>>ConstructPassages(int N, const std::vector<std::pair<int,int>>&ES)
{
	n=N;
	int res=0;
	for (int i=1;i<=(n<<1);++i) depth[i]=GetDistance(1,i),res=max(res,depth[i]);
	for (int i=0;i<ES.size();++i)
	{
		if (depth[ES[i].first]+1==depth[ES[i].second]) E[ES[i].first].push_back(ES[i].second),used[ES[i].second]=1;
		if (depth[ES[i].second]+1==depth[ES[i].first]) E[ES[i].second].push_back(ES[i].first),used[ES[i].first]=1;
	}
	for (int i=1;i<=(n<<1);++i)
	{
		sp[depth[i]].push_back(i);
		if (!used[i]) p[depth[i]].push_back(i);
	}
	for (int i=1;i<=res;++i) solve(sp[i-1],p[i]);
	dfs(1);
	return ans;
}