#include "split.h"
#include <bits/stdc++.h>
std::vector <int> find_split(int n, int _a, int _b, int _c, std::vector <int> _u, std::vector <int> _v) {
std::vector <std::pair <int, int>> s = { { _a, 1 }, { _b, 2 }, { _c, 3 } };
std::sort(s.begin(), s.end());
std::vector <std::vector <int>> g(n);
int m = _u.size();
for (int i = 0; i < m; i++) {
g[_u[i]].push_back(_v[i]);
g[_v[i]].push_back(_u[i]);
}
if (s[0].first == 1) {
std::vector <int> ans(n, s[2].second);
auto dfs = [&] (auto&& self, int node, int& left) -> void {
if (!left || ans[node] != s[2].second) {
return;
}
left--;
ans[node] = s[1].second;
for (int x : g[node]) {
if (left) {
self(self, x, left);
}
}
};
int tmp = s[1].first;
dfs(dfs, 0, tmp);
for (int i = 0; i < n; i++) {
if (ans[i] == s[2].second) {
ans[i] = s[0].second;
break;
}
}
return ans;
}
std::vector <int> sub(n), ans(n, s[2].second);
auto fil = [&] (auto&& self, int node, int par, int col, int& left) -> void {
if (!left) {
return;
}
left--;
ans[node] = col;
for (int x : g[node]) {
if (x == par) {
continue;
}
self(self, x, node, col, left);
}
};
auto dfs = [&] (auto&& self, int node, int par) -> bool {
sub[node] = 1;
for (int x : g[node]) {
if (x == par) {
continue;
}
if (self(self, x, node)) {
return true;
}
sub[node] += sub[x];
}
for (int x : g[node]) {
if (x == par) {
continue;
}
if (sub[x] >= s[0].first && n - sub[x] >= s[1].first) {
int tmp = s[0].first;
fil(fil, x, node, s[0].second, tmp);
tmp = s[1].first;
fil(fil, node, x, s[1].second, tmp);
return true;
}
if (sub[x] >= s[1].first && n - sub[x] >= s[0].first) {
int tmp = s[1].first;
fil(fil, x, node, s[1].second, tmp);
tmp = s[0].first;
fil(fil, node, x, s[0].second, tmp);
return true;
}
}
return false;
};
if (!dfs(dfs, 0, -1)) {
return std::vector <int> (n, 0);
}
return ans;
}
