#include "split.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> find_split(int n, int a_, int b_, int c_, vector<int> pp, vector<int> q) {
vector<int> res(n);
vector<pair<int,int>> pts = {{a_, 1}, {b_, 2}, {c_, 3}};
sort(pts.begin(), pts.end());
int m = (int) pp.size();
vector<vector<int>> g(n);
for (int i = 0; i < m; ++i) {
g[pp[i]].push_back(q[i]);
g[q[i]].push_back(pp[i]);
}
if (a_ == 1) {
vector<pair<int,int>> ptss = {{b_, 2}, {c_, 3}};
sort(ptss.begin(), ptss.end());
vector<bool> vis(n);
auto [s, c] = ptss[0];
function<void(int)> Dfs = [&](int v) {
vis[v] = true;
--s;
res[v] = c;
for (int u : g[v]) {
if (!s) return;
if (!vis[u]) {
Dfs(u);
}
}
};
Dfs(0);
for (int i = 0; i < n; ++i) {
if (vis[i]) continue;
for (int u : g[i]) {
if (vis[u]) {
res[i] = 1;
for (int j = 0; j < n; ++j) {
if (!res[j]) {
res[j] = ptss[1].second;
}
}
return res;
}
}
}
return res;
}
vector<int> pr(n);
vector<int> sz(n);
function<void(int, int)> Dfs = [&](int v, int p) {
sz[v] = 1;
for (int u : g[v]) {
if (u != p) {
pr[u] = v;
Dfs(u, v);
sz[v] += sz[u];
}
}
};
Dfs(0, 0);
int s;
function<void(int, int, int)> color = [&](int v, int p, int c) {
res[v] = c;
--s;
for (int u : g[v]) {
if (!s) return;
if (u == p) continue;
color(u, v, c);
}
};
for (int i = 0; i < n; ++i) {
if (sz[i] >= pts[0].first && n - sz[i] >= pts[1].first) {
s = pts[0].first;
color(i, pr[i], pts[0].second);
s = pts[1].first;
color(pr[i], i, pts[1].second);
for (int j = 0; j < n; ++j) {
if (!res[j]) {
res[j] = pts[2].second;
}
}
break;
}
if (n - sz[i] >= pts[0].first && sz[i] >= pts[1].first) {
s = pts[1].first;
color(i, pr[i], pts[1].second);
s = pts[0].first;
color(pr[i], i, pts[0].second);
for (int j = 0; j < n; ++j) {
if (!res[j]) {
res[j] = pts[2].second;
}
}
break;
}
}
return res;
}
