#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,ps[SN+1],depth[SN+1],sz[SN+1];
bool vis[SN+1],vst[SN+1];
vector<int>E[SN+1];
vector<int>p[SN+1];
vector<int>tans;
vector<pair<int,int> >ans;
void add(int x,int y)
{
	E[x].push_back(y),E[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;
	sz[x]=vis[x];
	for (int i=0;i<E[x].size();++i) dfs2(E[x][i]),sz[x]+=sz[E[x][i]];
	if (!E[x].empty())
	{
		for (int i=1;i<=10;++i)
		{
			shuffle(E[x].begin(),E[x].end(),RAND),st.clear(),res=0;
			for (int j=0;j<E[x].size();++j)
			{
				st.push_back(E[x][j]),res+=sz[E[x][j]];
				if (res>1&&max(res,smz-res)<minn) rt=x,minn=max(res,smz-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)
	{
		for (int i=0;i<B.size();++i)
		{
			if (QueryLCA({B[i]},{A[0],A[1]},A[0])[0]) E[A[0]].push_back(B[i]);
			else E[A[1]].push_back(B[i]);
		}
		return;
	}
	minn=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>>&E)
{
	n=N;
	int res=0;
	for (int i=1;i<=(n<<1);++i) depth[i]=GetDistance(1,i),p[depth[i]].push_back(i),res=max(res,depth[i]);
	for (int i=1;i<=res;++i) solve(p[i-1],p[i]);
	dfs(1);
	return ans;
}