#include <bits/stdc++.h>
#include "split.h"
// #include "grader.cpp"
using namespace std;
const int N = 2e5 + 10;
int n, m, a, b, c, sz[N], par[N], comp_sz[4];
vector<int> g[N], seen, res;
void dfs(int v, int p = -1){
par[v] = p;
sz[v] = 1;
for (int u : g[v]){
if (u == p) continue;
dfs(u, v);
sz[v] += sz[u];
}
}
void get(int v, int x, int target, int p = -1){
seen.push_back(v);
for (int u : g[v]){
if (u == p or u == x) continue;
if (seen.size() < target)
get(u, x, target, v);
}
}
void get_sub(int v, int x, int target){
seen.push_back(v);
for (int u : g[v]){
if (u == par[v] or u == x) continue;
if (seen.size() < target)
get_sub(u, x, target);
}
}
// void reroot(int v, int p = -1){
// for (int u : g[v]){
// }
// }
vector<int> find_split(int nn, int aa, int bb, int cc, vector<int> p, vector<int> q) {
n = nn, a = aa, b = bb, c = cc, m = p.size();
comp_sz[1] = aa, comp_sz[2] = bb, comp_sz[3] = cc;
a = min({aa, bb, cc});
c = max({aa, bb, cc});
b = n - a - c;
for (int i = 0; i < m; i ++){
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
res.resize(n, 0);
int r = 0;
for (int i = 1; i < n; i ++)
if (g[r].size() < g[i].size())
r = i;
dfs(r);
for (int v = 0; v < n; v ++){
if (sz[v] >= a and n - sz[v] >= b){
get_sub(v, -1, a);
for (int col = 1; col <= 3; col ++){
if (comp_sz[col] == a){
for (int x : seen)
res[x] = col;
comp_sz[col] = -1;
break;
}
}
seen.clear();
get(r, v, b);
for (int col = 1; col <= 3; col ++){
if (comp_sz[col] == b){
for (int x : seen)
res[x] = col;
comp_sz[col] = -1;
break;
}
}
seen.clear();
for (int col = 1; col <= 3; col ++){
if (comp_sz[col] == -1) continue;
for (int i = 0; i < n; i ++)
if (!res[i])
res[i] = col;
}
return res;
}
}
return res;
}
