#include <bits/stdc++.h>
#include "split.h"
using namespace std;
vector <int> v[100000],arb[100000],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;
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&&!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 cnt=1;
where[nod]=cnt;
for(auto it:arb[nod])
if(it!=papa)
cnt+=dfscrip(it,nod);
return cnt;
}
void dfsnushce(int nod,int val)
{
cat+=vlu[nod].second;
marc2[nod]=val;
if(cat>=vec[0].second)
return;
for(auto it:much[nod])
if(!marc2[it])
dfsnushce(it,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);
int centr=-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[i]!=where[it])
much[where[i]].push_back(where[it]);
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)
{
ok=1;
for(j=1; j<=cnt; j++)
if(marc2[j]==cnt1)
dfscolor(vlu[j].first,centr,0);
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;
}
}
