#include "bits/stdc++.h"
#include "split.h"
using namespace std;
const int maxn = 1e5 + 10;
vector <int> graph[maxn];
vector <int> g[maxn];
vector <int> aux[maxn];
int sub[maxn];
int id[maxn];
bool vis[maxn];
vector <int> cont[maxn];
void makeTree(int x) {
vis[x] = true;
for(int i : graph[x]) {
if(vis[i] == false) {
g[x].push_back(i);
g[i].push_back(x);
makeTree(i);
}
}
}
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;
}
void assignId(int x, int par, int idx) {
id[x] = idx;
cont[idx].push_back(x);
for(int i : g[x]) {
if(i != par) {
assignId(i, x, idx);
}
}
}
void getNodes(int x, int &sum, vector <int> &v) {
if(sum <= 0) return ;
vis[x] = true;
v.push_back(x);
sum -= int(cont[x].size());
for(int i : aux[x]) {
if(vis[i] == false) {
getNodes(i, sum, v);
}
}
}
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);
}
fill(vis, vis + n, false);
for(int i = 0; i < p.size(); i++) {
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
}
makeTree(0);
dfs(0, -1);
int root = centroid(0, -1, n / 2);
for(int i : g[root]) {
assignId(i, root, i);
}
for(int i = 0; i < p.size(); i++) {
if(p[i] == root || q[i] == root) continue;
int x = id[p[i]];
int y = id[q[i]];
aux[x].push_back(y);
aux[y].push_back(x);
}
bool good = false;
auto assign = [&] (vector <int> v, int x, int valX) {
for(int i : v) {
if(x > 0) {
res[i] = valX;
x -= 1;
}
}
};
function <void(int, int&, int)> assignGraph = [&] (int x, int &cnt, int val) {
if(cnt <= 0) return ;
res[x] = val;
cnt -= 1;
vis[x] = true;
for(int i : graph[x]) {
if(vis[i] == false) {
assignGraph(i, cnt, val);
}
}
};
for(int i : g[root]) {
if(cont[i].size() >= a) {
good = true;
assign(cont[i], a, valA);
break;
}
}
if(not good) {
fill(vis, vis + n, false);
for(int i : g[root]) {
int tmp = a;
vector <int> v;
getNodes(i, tmp, v);
if(tmp <= 0) {
fill(vis, vis + n, true);
for(int j : v) for(int k : cont[j]) vis[k] = false;
assignGraph(i, a, valA);
break;
}
}
}
if(*max_element(res.begin(), res.end()) == 0) return res;
fill(vis, vis + n, false);
for(int i = 0; i < n; i++) if(res[i] != 0) vis[i] = true;
assignGraph(root, b, valB);
for(int i = 0; i < n; i++) if(res[i] == 0) res[i] = valC;
return res;
}
