#include <iostream>
#include <vector>
using namespace std;
const int N = 1<<18;
int seen[N], ch[N], ca, cb, cc;
vector<int> nei[N], vec, vec1, vec2;
int dfs1(int u, int lim){
if (lim == 0)
return 0;
seen[u] = 1;
lim--;
vec.push_back(u);
for (int i : nei[u]){
if (seen[i] == 0)
lim = dfs1(i, lim);
}
return lim;
}
void dfs2(int u, int p){
ch[u] = 1;
for (int i : nei[u]){
if (i != p)
dfs2(i, u), ch[u] += ch[i];
}
}
bool T = 0;
void dfs3(int u, int p, int A, int B){
if (T)
return;
if (ch[u] >= A and ch[0] - ch[u] >= B){
seen[p] = 1;
dfs1(u, A);
vec1 = vec, vec = {};
seen[p] = 0;
dfs1(p, B);
vec2 = vec;
T = 1;
}
else if (ch[u] >= B and ch[0] - ch[u] >= A){
seen[u] = 1;
dfs1(p, A);
vec1 = vec, vec = {};
seen[u] = 0;
dfs1(u, B);
vec2 = vec;
T = 1;
}
for (int i : nei[u]){
if (i != p)
dfs3(i, u, A, B);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> u, vector<int> v){
for (int i=0;i<u.size();i++){
nei[u[i]].push_back(v[i]);
nei[v[i]].push_back(u[i]);
}
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);
int mx = 0;
for (int i=0;i<n;i++)
mx = max(mx, (int)nei[i].size());
vector<int> ans(n, cc);
if (a == 1){
dfs1(0, b);
for (int i : vec)
ans[i] = cb;
for (int i=0;i<n and a;i++){
if (ans[i] == cc)
ans[i] = ca, a = 0;
}
return ans;
}
if (u.size() == n and mx == 2){
int VV = nei[0][1];
nei[0].pop_back();
if (nei[VV][0] == 0)
swap(nei[VV][0], nei[VV][1]);
nei[VV].pop_back();
}
dfs2(0, 0);
dfs3(0, n, a, b);
for (int i : vec1)
ans[i] = ca;
for (int i : vec2)
ans[i] = cb;
if (T == 1)
return ans;
return vector<int> (n, 0);
}
