#include "split.h"
#include <bits/stdc++.h>
using namespace std;
struct cell
{
int st,ind;
};
bool cmp(cell a1, cell a2)
{
return a1.st<a2.st;
}
vector<int>v[200005],g[200005],otg;
int used[200005],sz[200005],n,center,br[200005],lead[200005],bb;
cell t[10];
map<pair<int,int>,int>ma;
void create_tree(int beg)
{
used[beg]=1;
int w;
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i];
if(!used[w])
{
g[beg].push_back(w);
g[w].push_back(beg);
ma[{beg,w}]=1;
ma[{w,beg}]=1;
create_tree(w);
}
}
}
void get_sz(int beg,int par)
{
sz[beg]=1;
int w;
for(int i=0;i<g[beg].size();i++)
{
w=g[beg][i];
if(w!=par)
{
get_sz(w,beg);
sz[beg]+=sz[w];
}
}
}
int get_centroid(int beg,int par)
{
int w;
for(int i=0;i<g[beg].size();i++)
{
w=g[beg][i];
if(w==par)continue;
if(sz[w]>=n/2)
{
return get_centroid(w,beg);
}
}
return beg;
}
void prec(int beg,int par,int lea)
{
//cout<<beg<<" "<<par<<" "<<lea<<endl;
int w;
lead[beg]=lea;
br[lea]++;
for(int i=0;i<g[beg].size();i++)
{
w=g[beg][i];
if(w!=par)
{
prec(w,beg,lea);
}
}
}
int get_lead(int beg)
{
if(lead[beg]==beg)return beg;
return lead[beg]=get_lead(lead[beg]);
}
int merg(int a,int b)
{
a=get_lead(a);
b=get_lead(b);
if(a==b)return 0;
if(br[a]<br[b])swap(a,b);
br[a]+=br[b];
lead[b]=a;
return 1;
}
void get_ans(int beg,int par,int con)
{
int w;
used[beg]=1;
otg[beg-1]=con;
bb--;
//cout<<beg<<" "<<par<<" "<<con<<" "<<bb<<endl;
for(int i=0;i<g[beg].size();i++)
{
if(!bb)return;
w=g[beg][i];
if(w==par||used[w])continue;
get_ans(w,beg,con);
}
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q)
{
t[1]={a,1};
t[2]={b,2};
t[3]={c,3};
n=N;
sort(t+1,t+4,cmp);
for(int i=0;i<p.size();i++)
{
p[i]++;
q[i]++;
v[p[i]].push_back(q[i]);
v[q[i]].push_back(p[i]);
}
//cout<<endl<<endl<<endl;
create_tree(1);
/*for(int i=1;i<=n;i++)
{
cout<<i<<" : ";
for(int j=0;j<g[i].size();j++)
{
cout<<g[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;*/
get_sz(1,1);
center=get_centroid(1,1);
//cout<<center<<endl;
for(int i=1;i<=n;i++)
{
sz[i]=0;
used[i]=0;
}
get_sz(center,center);
for(int i=0;i<g[center].size();i++)
{
prec(g[center][i],center,g[center][i]);
//cout<<endl<<endl;
}
int masz=0,ind=0,to=0;
for(int i=1;i<=n;i++)
{
otg.push_back(0);
if(br[i]>masz)
{
masz=br[i];
ind=i;
}
}
int lamp=0;
while(masz<t[1].st)
{
for(int i=to;i<p.size();i++)
{
if(p[i]==center||q[i]==center)continue;
if(!ma[{p[i],q[i]}])
{
if(merg(p[i],q[i])==0)continue;
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
ma[{p[i],q[i]}]=1;
ma[{q[i],p[i]}]=1;
to=i+1;
if(masz<br[get_lead(p[i])])
{
masz=br[get_lead(p[i])];
ind=get_lead(p[i]);
}
break;
}
if(i==p.size())
{
lamp=1;
break;
}
}
}
if(lamp)
{
return otg;
}
else
{
used[center]=1;
bb=t[1].st;
get_ans(ind,ind,t[1].ind);
bb=t[2].st;
get_ans(center,center,t[2].ind);
for(int i=1;i<=n;i++)
{
if(!used[i])
{
otg[i-1]=t[3].ind;
}
}
}
return otg;
}
