#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) {
int m = _u.size();
std::vector <std::pair <int, int>> s = { { _a, 1 }, { _b, 2 }, { _c, 3 } };
std::sort(s.begin(), s.end());
std::vector <int> ans(n, s[2].second);
std::vector <std::vector <int>> g(n);
std::vector <std::vector <int>> h(n);
for (int i = 0; i < m; i++) {
g[_u[i]].push_back(_v[i]);
g[_v[i]].push_back(_u[i]);
}
std::vector <int> sub(n, 1);
std::vector <int> dep(n, 0);
std::vector <int> fur(n, 1 << 30);
std::vector <bool> vis(n, false);
std::vector <bool> stop(n, false);
auto ini = [&] (auto&& self, int node) -> void {
vis[node] = true;
for (int x : g[node]) {
if (!vis[x]) {
dep[x] = dep[node] + 1;
self(self, x);
sub[node] += sub[x];
h[node].push_back(x);
} else {
fur[node] = std::min(fur[node], dep[x]);
}
}
};
ini(ini, 0);
std::vector <int> toc;
auto rem = [&] (auto&& self, int node, int& mine, int& rest, int upp) -> void {
if (fur[node] < upp && mine - sub[node] >= s[0].first) {
stop[node] = true;
toc.push_back(node);
mine -= sub[node];
rest += sub[node];
return;
}
for (int x : h[node]) {
self(self, x, mine, rest, upp);
}
};
auto mak1 = [&] (auto&& self, int node, std::vector <bool>& ok) -> void {
if (stop[node] || !s[0].first) {
return;
}
ok[node] = false;
ans[node] = s[0].second;
s[0].first--;
for (int x : h[node]) {
self(self, x, ok);
}
};
auto mak2 = [&] (auto&& self, int node, const std::vector <bool>& ok, std::vector <bool>& vs) -> void {
if (!ok[node] || vs[node] || !s[1].first) {
return;
}
vs[node] = true;
ans[node] = s[1].second;
s[1].first--;
for (int x : g[node]) {
self(self, x, ok, vs);
}
};
auto dfs = [&] (auto&& self, int node) -> bool {
bool all_less = true;
for (int x : h[node]) {
if (sub[x] >= s[0].first) {
all_less = false;
if (self(self, x)) {
return true;
}
}
}
if (all_less) {
int mine = sub[node];
int rest = n - sub[node];
rem(rem, node, mine, rest, dep[node]);
if (rest >= s[1].first) {
std::vector <bool> ok(n, true);
std::vector <bool> vs(n, false);
mak1(mak1, node, ok);
assert(ans[0] == s[2].second);
mak2(mak2, 0, ok, vs);
return true;
}
for (int x : toc) {
stop[x] = false;
}
toc.clear();
}
return false;
};
if (!dfs(dfs, 0)) {
std::swap(s[0], s[1]);
if (!dfs(dfs, 0)) {
return std::vector <int> (n, 0);
}
}
return ans;
}
