#include <bits/stdc++.h>
#include "split.h"
template <class T> using Vec = std::vector<T>;
template <class F> struct RecLambda: private F {
explicit RecLambda(F&& f): F(std::forward<F>(f)) {}
template <class... Args> decltype(auto) operator () (Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
struct Node {
Vec<int> adjacent, children, tree;
int parent, ord, low, subtree;
Node() = default;
};
Vec<int> find_split(int n, int a, int b, int c, Vec<int> edge_p, Vec<int> edge_q) {
std::array<int, 4> specified_size = {-1, a, b, c};
std::array<int, 3> size_order = {1, 2, 3};
std::sort(size_order.begin(), size_order.end(), [&](const int i, const int j) {
return specified_size[i] < specified_size[j];
});
const auto [small, medium, big] = size_order;
const auto small_sz = specified_size[small];
const auto medium_sz = specified_size[medium];
Vec<Node> node(n);
for (int i = 0; i < (int) edge_p.size(); ++i) {
const auto u = edge_p[i];
const auto v = edge_q[i];
node[u].adjacent.push_back(v);
node[v].adjacent.push_back(u);
}
{
int timer = 0;
RecLambda([&](auto&& dfs, const int u, const int p) -> void {
node[u].parent = p;
node[u].ord = node[u].low = timer;
timer += 1;
node[u].subtree = 1;
for (const auto v: node[u].adjacent) {
if (v == p) {
continue;
}
if (node[v].subtree == 0) {
dfs(v, u);
node[u].children.push_back(v);
node[u].subtree += node[v].subtree;
node[u].low = std::min(node[u].low, node[v].low);
} else {
node[u].low = std::min(node[u].low, node[v].ord);
}
}
node[u].tree = node[u].children;
if (p != -1) {
node[u].tree.push_back(p);
}
})(0, -1);
}
Vec<int> ret(n);
const auto write = RecLambda([&](auto&& dfs, const int u, const int p, const int w, int& c) -> void {
if (c == 0 or ret[u] != 0) {
return;
}
ret[u] = w;
c -= 1;
for (const auto v: node[u].tree) {
if (v != p) {
dfs(v, u, w, c);
}
}
});
for (int u = 0; u < n; ++u) {
int p_sz = n - node[u].subtree;
Vec<std::pair<int, int>> around;
for (const auto v: node[u].children) {
if (node[v].low < node[u].ord) {
p_sz += node[v].subtree;
} else {
around.emplace_back(node[v].subtree, v);
}
}
if (p_sz != 0) {
assert(node[u].parent != -1);
around.emplace_back(p_sz, node[u].parent);
}
bool less_a = true;
const int len = (int) around.size();
for (int i = 0; i < len; ++i) {
const auto [s, v] = around[i];
if (s >= small_sz) {
less_a = false;
}
if (s >= small_sz and n - s >= medium_sz) {
int tmp = small_sz;
write(v, u, small, tmp);
tmp = medium_sz;
write(u, v, medium, tmp);
goto finish;
}
if (s >= medium_sz and n - s >= small_sz) {
int tmp = small_sz;
write(u, v, small, tmp);
tmp = medium_sz;
write(v, u, medium, tmp);
goto finish;
}
}
if (less_a) {
goto finish;
}
}
RecLambda([&](auto&& dfs, const int u) -> void {
int upper = n - node[u].subtree;
if (upper >= a) {
int tmp = small_sz;
write(node[u].parent, u, small, tmp);
tmp = medium_sz;
write(u, node[u].parent, medium, tmp);
return;
}
for (const auto v: node[u].children) {
if (node[v].subtree >= medium_sz) {
dfs(medium_sz);
return;
}
if (node[v].subtree >= small_sz) {
int tmp = small_sz;
write(v, u, small, tmp);
tmp = medium_sz;
write(u, v, medium, tmp);
return;
}
}
Vec<int> seen;
for (const auto v: node[u].children) {
if (node[v].low < node[u].ord) {
upper += node[v].subtree;
seen.push_back(v);
}
if (upper >= small_sz) {
break;
}
}
if (upper >= medium_sz) {
int tmp = medium_sz;
write(node[u].parent, u, medium, tmp);
for (const auto v: seen) {
write(v, u, medium, tmp);
}
tmp = small_sz;
write(u, node[u].parent, small, tmp);
} else {
int tmp = small_sz;
write(node[u].parent, u, small, tmp);
for (const auto v: seen) {
write(v, u, small, tmp);
}
tmp = medium_sz;
write(u, node[u].parent, medium, tmp);
}
});
finish:
if (std::any_of(ret.begin(), ret.end(), [&](const int x) { return x != 0; })) {
for (auto& x: ret) {
if (x == 0) {
x = big;
}
}
}
return ret;
}
