#include "split.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> e[100010];
vector<int> res;
int n,a,b,c,cor[3],ok;
void color(int now,int c,int &num){
if(num==0)return;
res[now]=c;
num--;
for(auto x:e[now]){
if(res[x])continue;
color(x,c,num);
if(num==0)return;
}
return;
}
int dfs(int now,int last){
if(ok)return 0;
int sz=1;
for(auto x:e[now]){
if(x==last)continue;
sz+=dfs(x,now);
if(ok)return 0;
}
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
if(ok)continue;
if(i==j)continue;
if(sz>=cor[i-1]&&n-sz>=cor[j-1]){
res[now]=i,color(now,i,cor[i-1]);
res[last]=j,color(last,j,cor[j-1]);
for(int k=0;k<n;k++){
if(res[k]==0)res[k]=6-i-j;
}
ok=1;
}
}
}
return sz;
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
n=N;
int a=A,b=B,c=C;
cor[0]=a,cor[1]=b,cor[2]=c;
res.resize(n);
for(int i=0;i<p.size();i++){
e[p[i]].push_back(q[i]);
e[q[i]].push_back(p[i]);
}
dfs(0,0);
return res;
}
