#include<bits/stdc++.h>
#include "split.h"
using namespace std;
vector<int> ans;
vector<int> adj[100000];
vector<int> sub(100000, 1);
vector<int> d(100005, 0);
void dfs(int x, int pre){
for(auto y : adj[x]){
if(y == pre) continue;
d[y] = d[x] + 1;
dfs(y, x);
sub[x] += sub[y];
}
}
void greedy(int x, int& rem, int v){
if(!rem) return;
ans[x] = v;
rem--;
for(auto y : adj[x]){
if(ans[y]) continue;
greedy(y, rem, v);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> u, vector<int> v) {
ans = vector<int>(n, 0);
int w[3] = {a, b, c};
vector<int> q = {0, 1, 2};
sort(q.begin(), q.end(), [&](int x, int y){return w[x] < w[y];});
for(int i = 0; i < u.size(); i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0, -1);
vector<int> seq(n);
for(int i = 0; i < n; i++){
seq[i] = i;
}
sort(seq.begin(), seq.end(), [&](int x, int y){return sub[x] < sub[y];});
int t1 = 0, t2 = 0;
for(auto x : seq){
if(sub[x] >= w[q[0]]){
t1 = x;
break;
}
}
for(auto x : seq){
if(sub[x] >= w[q[1]]){
t2 = x;
break;
}
}
if(n - sub[t1] >= w[q[1]]){
ans[t1] = q[0] + 1;
greedy(0, w[q[1]], q[1] + 1);
greedy(t1, w[q[0]], q[0] + 1);
}
else if(n - sub[t2] >= w[q[0]]){
ans[t2] = q[1] + 1;
greedy(0, w[q[0]], q[0] + 1);
greedy(t2, w[q[1]], q[1] + 1);
}
else{
return ans;
}
for(int i = 0; i < n; i++){
if(!ans[i]) ans[i] = q[2] + 1;
}
return ans;
}
