#include <bits/stdc++.h>
#include "split.h"
using namespace std;
vector <int> v[100000];
int rez[100000],mar[100000];
int a,b,c;
void dfscolor(int nod,int papa,int col)
{
rez[nod]=col;
for(auto it:v[nod])
if(it!=papa)
dfscolor(it,nod,col);
}
void dfs(int nod,int papa)
{
if(min(a,min(b,c))==0)
return;
mar[nod]=1;
for(auto it:v[nod])
if(it!=papa)
{
dfs(it,nod);
mar[nod]+=mar[it];
}
if(mar[nod]==a)
{
a=0;
mar[nod]=0;
dfscolor(nod,papa,1);
return;
}
if(mar[nod]==b)
{
b=0;
mar[nod]=0;
dfscolor(nod,papa,2);
return;
}
if(mar[nod]==c)
{
c=0;
mar[nod]=0;
dfscolor(nod,papa,3);
return;
}
}
void dfsnew(int nod,int papa,int col,int &a)
{
if(!a)
return;
a--;
rez[nod]=col;
for(auto it:v[nod])
if(it!=papa&&!rez[it])
dfsnew(it,nod,col,a);
}
vector<int> find_split(int n, int A, int B, int C, vector<int> p, vector<int> q)
{
a=A;
b=B;
c=C;
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);
vector <int> ans;
if(min(a,min(b,c))!=0)
{
for(i=0; i<n; i++)
ans.push_back(0);
return ans;
}
for(i=0; i<n; i++)
if(!rez[i])
{
if(a)
dfsnew(i,-1,1,a);
else if(b)
dfsnew(i,-1,2,b);
else
dfsnew(i,-1,3,c);
}
for(i=0; i<n; i++)
if(!rez[i])
{
if(a)
rez[i]=1;
if(b)
rez[i]=2;
if(c)
rez[i]=3;
}
for(i=0; i<n; i++)
ans.push_back(rez[i]);
return ans;
}
