#include "split.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define f first
#define s second
const int N = 1e5 + 10;
int was[N], sz[N], ans[N], cnt;
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 c){
if(cnt <= 0 || ans[u] != 0)
return;
ans[u] = c;
--cnt;
for(auto v : tr[u])
if(v != pr && ans[v] == 0)
paint(v, u, c);
}
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, pair<int, int> a, pair<int, int> b, pair<int, int> c){
for(auto v : tr[u])
if(v != pr)
if(dfs(v, u, a, b, c))
return true;
if(sz[u] >= b.f && sz[u] <= b.f + c.f){
cnt = b.f;
paint(u, pr, b.s);
return true;
}
return false;
}
vector<int> solve(int n, pair<int, int> a, pair<int, int> b, pair<int, 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)){
// for(int i = 0; i < n; ++i)
// cout << ans[i] << " ";
// cout << endl;
cnt = a.f;
paint(0, -1, a.s);
for(int i = 0; i < n; ++i)
res[i] = (ans[i] == 0 ? c.s : 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;
vector<pair<int, int>> pr;
pr.pb({a, 1}), pr.pb({b, 2}), pr.pb({c, 3});
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;
}
