#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 2e5+10;
vector<int> ans;
int N,A,B,C;
int sz[mxn];
vector<int> tree[mxn];
vector<int> perm;
vector<int> tar;
void dfs(int now,int par){
sz[now] = 1;
for(auto nxt:tree[now]){
if(nxt == par)continue;
dfs(nxt,now);
sz[now] += sz[nxt];
}
return;
}
int find_centroid(int now,int par,int tar){
for(auto nxt:tree[now]){
if(nxt == par)continue;
if(sz[nxt]>tar)return find_centroid(nxt,now,tar);
}
return now;
}
void color(int now,int par,int &cnt,int col){
if(!cnt)return;
cnt--;
ans[now] = col;
for(auto nxt:tree[now]){
if(nxt == par)continue;
color(nxt,now,cnt,col);
}
return;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
ans = vector<int>(n,0);
N = n,A = a,B = b,C = c;
tar = {A,B,C};
perm = {0,1,2};
sort(perm.begin(),perm.end(),[&](int a,int b){return tar[a]<tar[b];});
sort(tar.begin(),tar.end());
for(int i = 0;i<p.size();i++){
int a = p[i],b = q[i];
tree[a].push_back(b);
tree[b].push_back(a);
}
dfs(0,0);
int cen = find_centroid(0,0,sz[0]>>1);
dfs(cen,cen);
sort(tree[cen].begin(),tree[cen].end(),[](int a,int b){return sz[a]<sz[b];});
ans[cen] = perm[1]+1;
tar[1]--;
for(auto nxt:tree[cen]){
color(nxt,cen,tar[1],perm[1]+1);
}
int big = tree[cen].back();
if(sz[big]<tar[0])return vector<int>(N,0);
color(big,cen,tar[0],perm[0]+1);
for(auto &i:ans)if(!i)i = perm[2]+1;
return ans;
}
