#include "split.h"
#include <bits/stdc++.h>
#define LL long long
#define F first
#define S second
using namespace std;
const int N = 2e5+10;
const LL INF = 1e9;
vector<int>adj[N],ans;
int n,m,sizes[N],vis[N],par[N],a,b,c,mn = INF;
pair<int,pair<int,int>>p1;
vector<pair<int,int>>vec;
void dfs(int i,int pre){
sizes[i] = 1;par[i] = pre;
for(auto x:adj[i])
if(x!=pre)
dfs(x,i),sizes[i] += sizes[x];
if(sizes[i]>=a&&sizes[i]-a<mn)
mn = sizes[i]-a,p1 = make_pair(i,make_pair(a,1));
if(sizes[i]>=b&&sizes[i]-b<mn)
mn = sizes[i]-b,p1 = make_pair(i,make_pair(b,2));
if(sizes[i]>=c&&sizes[i]-c<mn)
mn = sizes[i]-c,p1 = make_pair(i,make_pair(c,3));
}
void color(int i,int c,int &cnt){
if(vis[i]||!cnt)
return ;
vis[i] = 1,ans[i] = c;
cnt--;
for(auto x:adj[i])
color(x,c,cnt);
}
int cnt[4];
void f(){
dfs(0,n);
vis[par[p1.F]] = 1;
color(p1.F,p1.S.S,p1.S.F);
vis[par[p1.F]] = 0;
for(int i=0;i<3;i++)
if(p1.S.S!=vec[i].S){
color(0,vec[i].S,vec[i].F);
break;
}
for(int i=0;i<n;i++)
cnt[ans[i]]++;
int col = 0;
for(int i=1;i<4;i++)
if(!cnt[i])col = i;
for(int i=0;i<n;i++)
if(!ans[i])ans[i] = col,cnt[col]++;
if(cnt[1]!=a||cnt[2]!=b||cnt[3]!=c)
ans = vector<int>(n,0);
}
vector<int> find_split(int n1, int a1, int b1, int c1, vector<int> p, vector<int> q) {
n = n1; m = p.size(); a = a1; b = b1; c = c1;
ans = vector<int>(n,0);
vec.push_back({a,1}); vec.push_back({b,2}); vec.push_back({c,3});
sort(vec.begin(),vec.end());
for(int i=0;i<m;i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
f();
return ans;
}
