#include "split.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> g;
vector<int> v;
vector<int> pa;
vector<int> res;
int x, y;
int dfs(int cur, int par){
pa[cur] = par;
for (int next : g[cur]){
if (next != par) v[cur] += dfs(next, cur);
}
return v[cur];
}
void fill(int cur, int blk, int c){
if (x == y) return;
res[cur] = c;
y++;
for (int next : g[cur]){
if (next != blk && next != pa[cur]) fill(next, blk, c);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
vector<int> w = {1, 2, 3};
if (b > c){
swap(b, c);
swap(w[1], w[2]);
}
if (a > b){
swap(a, b);
swap(w[0], w[1]);
}
if (b > c){
swap(b, c);
swap(w[1], w[2]);
}
g.resize(n);
for (int i=0; i<n-1; i++){
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
v.resize(n, 1);
pa.resize(n);
dfs(0, 0);
for (int i=0; i<n; i++){
if (max(v[i], n-v[i]) >= b && min(v[i], n-v[i]) >= a){
res.resize(n, w[2]);
if (v[i] < n-v[i]){
x = a;
y = 0;
fill(i, -1, w[0]);
x = b;
y = 0;
fill(0, i, w[1]);
}
else {
x = a;
y = 0;
fill(0, i, w[0]);
x = b;
y = 0;
fill(i, -1, w[1]);
}
return res;
}
}
res.resize(n, -1);
return res;
}
