#include "bits/stdc++.h"
#include "split.h"
// #include "grader.cpp"
using namespace std;
#define ll long long
#define SZ(s) s.size()
#define ff first
#define ss second
const int N = 2e5 + 5;
int n, ind = -1, cnt;
vector <int> v[N], u[N], vis, p, d, deg, vn, res;
vector <pair <int, int>> v1;
int bld(int x, int y) {
p[x] = y;
d[x] = vis[x] = true;
for(auto i : v[x]) {
if(!vis[i]) {
u[x].push_back(i);
d[x] += bld(i, x);
}
}
return d[x];
}
void dfs(int x) {
bool tr = 0;
for(auto i : u[x]) {
if(i == p[x]) continue;
if(d[i] >= v1[0].ff) {
dfs(i);
tr = 1;
}
}
if(tr) return;
queue <int> q, b;
q.push(x);
while(!q.empty()) {
int y = q.front();
q.pop();
bool tr1 = 0;
for(auto i : v[y]) {
if(p[i] != y and i != p[y] and !tr1) {
b.push(y);
tr1 = true;
}
}
for(auto i : u[y]) {
q.push(i);
}
}
int k = (n - d[x]);
while(!b.empty() and k < v1[1].ff) {
int y = b.front();
b.pop();
vn[y] = true;
if(p[y] == -1) continue;
deg[p[y]]++;
if(deg[p[y]] == SZ(u[p[y]])) b.push(p[y]);
k++;
}
if(k >= v1[1].ff) ind = x;
}
void f() {
for(int i = 0; i < n; i++) {
u[i].clear();
}
vis.assign(n, 0), p.assign(n, 0), d.assign(n, 0), deg.assign(n, 0), vn.assign(n, 0);
bld(0, -1);
dfs(0);
}
void df(int x) {
if(!cnt) return;
res[x] = v1[0].ss;
cnt--;
for(auto i : u[x]) {
if(!vn[i]) df(i);
}
}
void df1(int x) {
if(!cnt) return;
res[x] = v1[1].ss;
cnt--;
for(auto i : v[x]) {
if(!res[i]) df1(i);
}
}
vector <int> f1() {
cnt = v1[0].ff;
df(ind);
cnt = v1[1].ff;
df1(p[ind]);
for(int i = 0; i < n; i++) {
if(!res[i]) res[i] = v1[2].ss, cnt++;
}
return res;
}
vector<int> find_split(int NN, int a, int b, int c, vector<int> u1, vector<int> u2) {
n = NN;
int m = SZ(u1);
for(int i = 0; i < m; i++) {
v[u1[i]].push_back(u2[i]);
v[u2[i]].push_back(u1[i]);
}
v1.push_back({a, 1});
v1.push_back({b, 2});
v1.push_back({c, 3});
sort(v1.begin(), v1.end());
res.assign(n, 0);
f();
if(~ind) return f1();
swap(v1[0], v1[1]);
f();
if(~ind) return f1();
return res;
}
