#include "split.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
const int N = 1e5 + 10;
int was[N], sz[N], ans[N];
vector<int> g[N], tr[N];
void build_dfs(int u){
was[u] = 1;
for(auto v : g[u])
if(was[v] == 0){
tr[u].pb(v), tr[v].pb(u);
build_dfs(v);
}
}
void paint(int u, int pr, int a, int c){
if(a <= 0)
return;
ans[u] = c;
--a;
for(auto v : tr[u])
if(v != pr){
paint(v, u, a, c);
a -= sz[v];
}
}
void sz_dfs(int u, int pr){
sz[u] = 1;
for(auto v : tr[u])
if(v != pr)
sz_dfs(v, u), sz[u] += sz[v];
}
bool dfs(int u, int pr, int a, int b, int c){
for(auto v : tr[u])
if(v != pr)
if(dfs(v, u, a, b, c))
return true;
if(sz[u] >= b && sz[u] <= b + c){
paint(u, pr, b, 2);
return true;
}
return false;
}
vector<int> solve(int n, int a, int b, int c){
for(int i = 0; i < n; ++i)
was[i] = sz[i] = 0, tr[i].clear();
build_dfs(0);
sz_dfs(0, -1);
vector<int> res(n, 0);
if(dfs(0, -1, a, b, c)){
paint(0, -1, a, 1);
for(int i = 0; i < n; ++i)
res[i] = (ans[i] == 0 ? 3 : ans[i]);
}
return res;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m = p.size();
for(int i = 0; i < m; ++i){
g[p[i]].pb(q[i]);
g[q[i]].pb(p[i]);
}
vector<int> res, pr;
pr.pb(a), pr.pb(b), pr.pb(c);
do{
res = solve(n, pr[0], pr[1], pr[2]);
if(res[0] != 0)
return res;
}while(next_permutation(pr.begin(), pr.end()));
return res;
}
