#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define mp make_pair
vector<vector<int>> adj;
vector<int> tam, val = {1, 2, 3};
int getSz(int ver, int prev = -1){
tam[ver] = 1;
for(auto u : adj[ver]){
if(u == prev)
continue;
tam[ver] += getSz(u, ver);
}
return tam[ver];
}
int getCentroid(int ver, int tot, int prev = -1){
for(auto u : adj[ver]){
if(u == prev)
continue;
if(tam[u] >= (tot + 1) / 2)
return getCentroid(u, tot, ver);
}
return ver;
}
void paint(int ver, vector<int>& qnt, vector<int>& res, int color, int prev = -1){
res[ver] = color;
qnt[color]--;
for(auto u : adj[ver]){
if(!qnt[color])
return;
if(u == prev)
continue;
paint(u, qnt, res, color, ver);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
adj.resize(n);
tam.resize(n);
vector<int> qnt = {0, a, b, c};
if(a > c){
swap(a, c);
swap(val[0], val[2]);
}
if(b > c){
swap(b, c);
swap(val[1], val[2]);
}
if(a > b){
swap(a, b);
swap(val[0], val[1]);
}
for(int i = 0; i < (int)p.size(); i++){
int a = p[i], b = q[i];
adj[a].pb(b);
adj[b].pb(a);
}
int centroid = getCentroid(0, getSz(0));
getSz(centroid);
vector<int> res(n, val[2]); res[centroid] = val[1]; qnt[val[1]]--;
bool ok = 0;
for(auto u : adj[centroid]){
if(ok){
if(!qnt[val[1]])
break;
paint(u, qnt, res, val[1], centroid);
continue;
}
if(tam[u] >= a){
paint(u, qnt, res, val[0], centroid);
ok = 1;
}
else if(qnt[val[1]])
paint(u, qnt, res, val[1]);
}
if(!ok)
for(auto& u : res)
u = 0;
return res;
}
