#include <bits/stdc++.h>
#include "split.h"
using namespace std;
vector<vector<int>> g;
vector<int> sz, parent, ans;
void dfs(int u, int p) {
parent[u] = p;
sz[u] = 1;
for (int v : g[u]) {
if (v == p) {
continue;
}
dfs(v, u);
sz[u] += sz[v];
}
}
int t;
void down(int u, int c) {
if (t == 0) {
return;
}
ans[u] = c;
t--;
for (int v : g[u]) {
if (v == parent[u]) {
continue;
}
if (ans[v] == 0) {
down(v, c);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
g.resize(n);
sz.resize(n);
ans.resize(n);
parent.resize(n);
for (int i = 0; i < n - 1; i++) {
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
dfs(0, -1);
vector<array<int, 2>> v = {{a, 1}, {b, 2}, {c, 3}};
sort(v.begin(), v.end());
for (int u = 0; u < n; u++) {
int x = sz[u];
int y = n - sz[u];
if (x >= v[0][0] && y >= v[1][0]) {
t = v[0][0]; down(u, v[0][1]);
t = v[1][0]; down(0, v[1][1]);
for (int i = 0; i < n; i++) {
if (ans[i] == 0) {
ans[i] = v[2][1];
}
}
return ans;
}
if (x >= v[1][0] && y >= v[0][0]) {
t = v[1][0]; down(u, v[1][1]);
t = v[0][0]; down(0, v[0][1]);
for (int i = 0; i < n; i++) {
if (ans[i] == 0) {
ans[i] = v[2][1];
}
}
return ans;
}
}
return ans;
}
