#include <bits/stdc++.h>
#include "split.h"
using namespace std;
vector <int> v[100000],arb[100000];
vector <pair<int,int>> much[100000];
pair <int,int> vec[3];
pair <int,int> vlu[100001];
int rez[100000],mar[100000],tata[100000],marc2[100000],where[100000],cnt,cat,cnt2,centr;
int coada[100000];
bool marc[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&&it!=centr&&!rez[it])
dfscolor(it,nod,ind);
}
void dfs(int nod,int papa)
{
mar[nod]=1;
tata[nod]=papa;
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 dfscrip(int nod,int papa)
{
int cnt1=1;
where[nod]=cnt;
for(auto it:arb[nod])
if(it!=papa)
cnt1+=dfscrip(it,nod);
return cnt1;
}
void dfsnushce(int nod,int val)
{
if(cat>=vec[0].first)
return;
cat+=vlu[nod].second;
marc2[nod]=val;
if(cat>=vec[0].first)
return;
for(auto it:much[nod])
if(cat<vec[0].first&&!marc2[it.first])
{
coada[++cnt2]=it.second;
dfsnushce(it.first,val);
}
}
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);
for(i=0; i<n; i++)
{
int max1=0,s=1;
for(auto it:arb[i])
if(it!=tata[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])
vlu[++cnt]= {it,dfscrip(it,centr)};
for(i=0; i<n; i++)
if(i!=centr)
for(auto it:v[i])
if(where[it]&&where[i]!=where[it])
much[where[i]].push_back({where[it],it});
/*for(i=1;i<=cnt;i++){
cout<<i<<" ";
for(auto it:much[i])
cout<<it.first<<" ";
cout<<'\n';
}*/
int cnt1=0,ok=0,j;
for(i=1; i<=cnt; i++)
if(!marc2[i])
{
cat=0;
dfsnushce(i,++cnt1);
if(cat>=vec[0].first)
{
//cout<<i<<" "<<cat<<'\n';
dfscolor(vlu[i].first,centr,0);
for(j=1; j<=cnt2; j++)
dfscolor(coada[j],-1,0);
ok=1;
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;
}
}
