#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,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) rt=x,minn=max(sz[x],smz-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) 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)
{
vector<int>v=query(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=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;
}