#include <iostream>
#include <vector>
using namespace std;
const int N = 1<<17;
vector<int> nei[N], adj[N], Ans;
vector<pair<int, int>> vec;
int hei[N], ch[N], seen[N], A, B, C, cA = 1, cB = 2, cC = 3;
pair<int, pair<int, int>> Mn[N];
void dfs1(int u, int p, int h, int mx = 0){
hei[u] = h;
ch[u] = 1;
Mn[u] = {h, {u, u}};
for (int i : nei[u]){
if (i == p)
continue;
if (hei[i]){
Mn[u] = min(Mn[u], {hei[i], {u, i}});
continue;
}
adj[u].push_back(i);
adj[i].push_back(u);
dfs1(i, u, h+1);
Mn[u] = min(Mn[u], Mn[i]);
ch[u] += ch[i];
mx = max(mx, ch[i]);
}
if (mx < A and ch[u] >= A)
vec.push_back({u, p});
}
int dfs2(int u, int p, int lim, int col){
if (lim == 0)
return 0;
seen[u] = 1, lim --;
Ans[u] = col;
for (int i : adj[u]){
if (!seen[i])
lim = dfs2(i, u, lim, col);
}
return lim;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> u, vector<int> v){
A = a, B = b, C = c, cA = 1, cB = 2, cC = 3;
if (A > B)
swap(A, B), swap(cA, cB);
if (A > C)
swap(A, C), swap(cA, cC);
if (B > C)
swap(B, C), swap(cB, cC);
for (int i=0;i<u.size();i++){
nei[u[i]].push_back(v[i]);
nei[v[i]].push_back(u[i]);
}
dfs1(0, 0, 1);
Ans.resize(n, cC);
for (auto [u, p] : vec){
vector<pair<int, int>> v;
int s = ch[0] - ch[u];
for (int i : nei[u]){
if (s < A and hei[i] == hei[u] + 1 and Mn[i].first < hei[u])
s += ch[i], v.push_back(Mn[i].second);
}
if (s < A)
continue;
for (auto [i, j] : v){
adj[i].push_back(j);
adj[j].push_back(i);
}
if (ch[0] - s >= B){
seen[u] = 1;
dfs2(p, p, A, cA);
seen[u] = 0;
dfs2(u, u, B, cB);
}
else{
seen[u] = 1;
dfs2(p, p, B, cB);
seen[u] = 0;
dfs2(u, u, A, cA);
}
return Ans;
}
return vector<int> (n, 0);
}
