#include "bits/stdc++.h"
#include "split.h"
using namespace std;
const int maxn = 1e5 + 10;
vector <int> g[maxn];
int sub[maxn];
void dfs(int x, int par) {
sub[x] = 1;
for(int i : g[x]) {
if(i != par) {
dfs(i, x);
sub[x] += sub[i];
}
}
}
int centroid(int x, int par, int range) {
for(int i : g[x]) {
if(i != par && range < sub[i]) {
return centroid(i, x, range);
}
}
return x;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector <int> res (n, 0);
int valA = 1, valB = 2, valC = 3;
if(a > b) {
swap(a, b);
swap(valA, valB);
}
if(b > c) {
swap(b, c);
swap(valB, valC);
}
if(a > b) {
swap(a, b);
swap(valA, valB);
}
for(int i = 0; i < p.size(); i++) {
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
dfs(0, -1);
int root = centroid(0, -1, n / 2);
dfs(root, -1);
function <void(int, int, vector <int> &)> getNodes = [&] (int x, int par, vector <int> &v) {
v.push_back(x);
for(int i : g[x]) {
if(i != par && res[i] == 0) {
getNodes(i, x, v);
}
}
return ;
};
for(int i : g[root]) {
if(sub[i] >= a) {
vector <int> v;
getNodes(i, root, v);
int tmp = a;
for(int j : v) {
if(tmp > 0) {
tmp -= 1;
res[j] = valA;
}
}
break;
}
}
if(*max_element(res.begin(), res.end()) == 0) return res;
vector <int> v;
getNodes(c, -1, v);
int tmp = b;
for(int i : v) {
if(tmp > 0) {
tmp -= 1;
res[i] = valB;
}
}
for(int i = 0; i < n; i++) if(res[i] == 0) res[i] = valC;
return res;
}
