#include "split.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
vector<int>v[maxn], filhos[maxn];
int marc[maxn], sub[maxn], pai[maxn], cor[maxn];
vector<int>ord;
void dfs(int u){
ord.push_back(u);
marc[u]++;
sub[u]=1;
for(int viz : v[u]){
if(marc[viz]) continue;
filhos[u].push_back(viz);
pai[viz]=u;
dfs(viz);
sub[u]+=sub[viz];
}
}
int calc(int u, int x, int c, int lim){
marc[u]++;
if(x){
cor[u]=c;
x--;
}
for(int viz : v[u]){
if(marc[viz]||viz==lim) continue;
x=calc(viz,x,c,lim);
}
return x;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
for(int i=0;i<p.size();i++){
v[p[i]].push_back(q[i]);
v[q[i]].push_back(p[i]);
}
dfs(1);
memset(marc,0,sizeof(marc));
vector<int>resp(n,0);
int alt=-1;
for(int i=1;i<=n;i++){
for(int x : filhos[i]){
if(sub[x]>=a&&n-sub[x]>=min(b,c)){
a=calc(x,a,1,i);
if(b<=c) b=calc(i,b,2,x), alt=3;
else c=calc(i,c,3,x), alt=2;
goto sair;
}
if(sub[x]>=b&&n-sub[x]>=min(a,c)){
b=calc(x,b,2,i);
if(a<=c) a=calc(i,a,1,x), alt=3;
else c=calc(i,c,3,x), alt=1;
goto sair;
}
if(sub[x]>=c&&n-sub[x]>=min(a,b)){
c=calc(x,c,3,i);
if(b<=a) b=calc(i,b,2,x), alt=1;
else a=calc(i,a,1,x), alt=2;
goto sair;
}
}
}
sair:;
for(int i=0;i<n;i++){
if(cor[i]) resp[i]=cor[i];
else if(alt!=-1) resp[i]=alt;
}
return resp;
}
