#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define sp << " " <<
vector<vector<int>> graph, tree;
vector<int> sbtree;
vector<bool> vis;
vector<int> res;
void dfs1(int n){
if (vis[n])
return;
vis[n] = true;
for (auto go : graph[n]){
if (vis[go])
continue;
tree[n].push_back(go);
dfs1(go);
sbtree[n] += sbtree[go];
}
}
int dfs2(int a, int color, int say){
if (res[a] || say == 0)
return say;
res[a] = color;
say--;
if (say == 0)
return 0;
for (auto go : tree[a]){
say = dfs2(go, color, say);
if (say == 0)
return 0;
}
return say;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m = p.size();
res.clear();
res.resize(n);
tree.resize(n);
graph.resize(n);
vis.resize(n, false);
sbtree.resize(n, 1);
for (int i = 0; i < m; i++){
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
}
dfs1(0);
int mn = min(a, min(a, b)), mnind = 0;
if (a == mn){
mnind = 1;
}else if (b == mn){
mnind = 2;
}else{
mnind = 3;
}
int ort = min(max(a, b), min(max(b, c), max(a, c))), ortind;
if (a == ort && mnind){
ortind = 1;
}else if (b == ort && mnind != 1){
ortind = 2;
}else{
ortind = 3;
}
int hid = 6 - mnind - ortind;
for (int i = 0; i < n; i++){
if (sbtree[i] >= mn && n - sbtree[i] >= ort){
dfs2(i, mnind, mn);
dfs2(0, ortind, ort);
for (int i = 0; i < n; i++){
if (res[i] == 0)
res[i] = hid;
}
break;
}else if (sbtree[i] >= ort && n - sbtree[i] >= mn){
dfs2(i, ortind, ort);
dfs2(0, mnind, mn);
for (int i = 0; i < n; i++){
if (res[i] == 0)
res[i] = hid;
}
break;
}
}
return res;
}
