#include <bits/stdc++.h>
#include "split.h"
using namespace std;
vector <int> v[100000],arb[100000];
pair <int,int> vec[3];
int rez[100000],mar[100000];
bool marc[100000];
int daddy[100000],sz[100000],strt[100000];
void dfscolor(int nod,int papa,int ind)
{
if(vec[ind].first==0)
return;
rez[nod]=vec[ind].second;
vec[ind].first--;
for(auto it:arb[nod])
if(it!=papa)
dfscolor(it,nod,ind);
}
void dfs(int nod,int papa)
{
mar[nod]=1;
for(auto it:v[nod])
if(it!=papa&&!mar[it])
{
arb[nod].push_back(it);
arb[it].push_back(nod);
dfs(it,nod);
mar[nod]+=mar[it];
}
}
void dfsnew(int nod,int papa)
{
mar[nod]=1;
for(auto it:arb[nod])
if(it!=papa)
{
dfsnew(it,nod);
mar[nod]+=mar[it];
}
}
int fada(int nod)
{
if(daddy[nod]==nod)
return nod;
return daddy[nod]=fada(daddy[nod]);
}
void join(int a,int b)
{
int ra=fada(a),rb=fada(b);
if(sz[ra]>sz[rb])
{
sz[ra]+=sz[rb];
daddy[rb]=ra;
strt[ra]+=strt[rb];
}
else
{
sz[rb]+=sz[ra];
daddy[ra]=rb;
strt[rb]+=strt[ra];
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
vec[0]= {a,1};
vec[1]= {b,2};
vec[2]= {c,3};
sort(vec,vec+3);
int i;
for(i=0; i<p.size(); i++)
{
v[p[i]].push_back(q[i]);
v[q[i]].push_back(p[i]);
}
dfs(0,-1);
int centr=-1;
for(i=0; i<n; i++)
{
int max1=0,s=1;
for(auto it:arb[i])
{
max1=max(max1,mar[it]);
s+=mar[it];
}
if(max(max1,n-s)<=n/2)
centr=i;
}
dfsnew(centr,-1);
for(auto it:arb[centr])
marc[it]=1;
for(i=0; i<n; i++)
{
daddy[i]=i;
sz[i]=1;
strt[i]=mar[i];
}
for(auto it:arb[centr])
for(auto it2:v[it])
if(marc[it2]&&fada(it2)!=fada(it))
join(it,it2);
int ok=0,where;
for(auto it:arb[centr])
if(strt[fada(it)]>=vec[0].first)
{
ok=1;
where=fada(it);
for(auto it2:arb[centr])
{
if(fada(it2)==fada(it))
dfscolor(it2,centr,0);
if(!vec[0].first)
break;
}
}
vector <int> ans;
ans.clear();
if(ok==0)
{
for(i=0; i<n; i++)
ans.push_back(0);
return ans;
}
else
{
dfscolor(centr,-1,1);
for(i=0; i<n; i++)
if(rez[i]==0)
rez[i]=vec[2].second;
for(i=0; i<n; i++)
ans.push_back(rez[i]);
return ans;
}
}
