#include "split.h"
#include<bits/stdc++.h>
using namespace std;
int cnt = 0;
vector<vector<int>> g, d;
vector<int> st, res;
void dfs(int cur){
if (st[cur] != -1) return;
st[cur] = 1;
for (int next : g[cur]){
if (st[next] != -1) continue;
dfs(next);
st[cur] += st[next];
d[cur].push_back(next);
}
}
void fill(int cur, int f, int x, int lim){
if (cur == f) return;
if (cnt >= lim) return;
res[cur] = x;
cnt++;
for (int next : d[cur]) fill(next, f, x, lim);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
g.resize(n);
for (int i=0; i<p.size(); i++){
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
d.resize(n);
st.resize(n, -1);
dfs(0);
vector<int> v = {1, 2, 3};
if (a > b){
swap(a, b);
swap(v[0], v[1]);
}
if (b > c){
swap(b, c);
swap(v[1], v[2]);
}
if (a > b){
swap(a, b);
swap(v[0], v[1]);
}
res.resize(n, 0);
for (int i=0; i<n; i++){
if (st[i] >= a && n-st[i] >= b){
res.assign(n, v[2]);
fill(i, -1, v[0], a);
fill(0, i, v[1], a+b);
break;
}
if (st[i] >= b && n-st[i] >= a){
res.assign(n, v[2]);
fill(i, -1, v[1], b);
fill(0, i, v[0], a+b);
break;
}
}
return res;
}
