#include <bits/stdc++.h>
#include "split.h"
using namespace std;
template <class F> struct rec_lambda : private F {
explicit rec_lambda(F&& f) : F(forward<F>(f)) {}
template <class... Args> decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, forward<Args>(args)...);
}
};
struct union_find {
vector<int> par;
explicit union_find(const int n) : par(n, -1) {}
int find(const int u) {
return par[u] < 0 ? u : par[u] = find(par[u]);
}
int size(const int u) {
return -par[find(u)];
}
bool same(const int x, const int y) {
return find(x) == find(y);
}
void merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (par[x] > par[y]) swap(x, y);
par[x] += par[y];
par[y] = x;
}
};
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
const array<int, 3> size = {a, b, c};
a = 0, b = 1, c = 2;
if (size[a] > size[b]) swap(a, b);
if (size[b] > size[c]) swap(b, c);
if (size[a] > size[b]) swap(a, b);
const int m = (int)p.size();
vector<vector<int>> graph(n);
for (int i = 0; i < m; ++i) {
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
}
vector<vector<int>> tree(n);
vector<char> done(n);
vector<int> subtree(n);
rec_lambda([&](auto&& dfs, const int u) -> void {
done[u] = true;
subtree[u] = 1;
for (const int v : graph[u]) {
if (!done[v]) {
tree[u].push_back(v);
tree[v].push_back(u);
subtree[u] += subtree[v];
dfs(v);
}
}
})(0);
int g = 0;
for (int p = -1;;) {
bool f = false;
for (const int u : tree[g]) {
if (u != p and subtree[u] * 2 > n) {
g = u;
f = true;
break;
}
}
if (!f) break;
}
union_find dsu(n);
int found = -1;
for (const int u : tree[g]) {
rec_lambda([&](auto&& dfs, const int u, const int p) -> void {
for (const int v : tree[u]) {
if (v != p) {
dsu.merge(u, v);
dfs(v, u);
}
}
})(u, g);
if (dsu.size(u) >= size[a]) found = u;
}
for (int i = 0; i < m; ++i) {
if (found != -1) break;
if (p[i] == g or q[i] == g) continue;
dsu.merge(p[i], q[i]);
if (dsu.size(p[i]) >= size[a]) found = p[i];
if (dsu.size(q[i]) >= size[a]) found = q[i];
}
vector<int> result(n);
if (found == -1) return result;
int count = size[a];
rec_lambda([&](auto&& dfs, const int u) -> void {
if (result[u] != 0 or !dsu.same(found, u) or count == 0) return;
result[u] = a + 1;
count -= 1;
for (const int v : graph[u]) dfs(v);
})(found);
count = size[b];
rec_lambda([&](auto&& dfs, const int u) -> void {
if (result[u] != 0 or count == 0) return;
result[u] = b + 1;
count -= 1;
for (const int v : graph[u]) dfs(v);
})(g);
for (auto& x : result) {
if (x == 0) x = c + 1;
}
return result;
}
