#include <bits/stdc++.h>
#include "split.h"
#define ll long long
#define ar array
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<vector<int>> adj(n);
int m = sz(p);
for (int i = 0; i < m; i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
vector<int> tin(n), low(n), stk;
vector<bool> ap(n);
vector<vector<int>> comps;
int timer = 0;
auto dfs = [&](auto&& s, int v, int p) -> void {
tin[v] = low[v] = ++timer;
stk.emplace_back(v);
for (int u : adj[v]) if (u != p) {
if (!tin[u]) {
s(s, u, v);
ckmin(low[v], low[u]);
if (low[u] >= tin[v]) {
ap[v] = 1;
comps.push_back({v});
for (int x = -1; x != u; ) {
x = stk.back();
stk.pop_back();
comps.back().push_back(x);
}
}
}
else ckmin(low[v], tin[u]);
}
};
dfs(dfs, 0, -1);
ar<int, 3> size{a, b, c}, ord{1, 2, 3};
sort(all(ord), [&](int x, int y) { return size[x-1] < size[y-1]; });
int c1 = ord[0], c2 = ord[1], A = size[ord[0]-1], B = size[ord[1]-1];
for (const auto& comp : comps) if (sz(comp) >= A + B) {
vector<bool> in(n);
for (int x : comp) in[x] = 1;
vector<int> ans(n, ord[2]);
vector<int> deg(n);
for (int x : comp) for (int u : adj[x]) if (in[u]) deg[u]++;
set<ar<int, 2>> q;
int who = min_element(all(deg)) - deg.begin();
q.insert({deg[who], who});
int got = 0;
while (q.size()) {
auto [_deg, v] = *q.begin();
q.erase(q.begin());
ans[v] = c1;
if (++got == A) break;
for (int u : adj[v]) if (in[u] && ans[u] == ord[2]) {
if (q.count({deg[u], u})) q.erase({deg[u], u});
deg[u]--;
q.insert({deg[u], u});
}
}
if (got != A) while (1) {}
assert(got == A);
auto dfs = [&](auto&& s, int v, int col, int target, int& got) -> void {
if (got >= target) return;
got++, ans[v] = col;
for (int u : adj[v]) {
deg[u]--;
}
while (got < target) {
int who = -1;
for (int u : adj[v]) if (in[u] && ans[u] == ord[2] && (!~who || deg[u] < deg[who])) who = u;
if (~who) s(s, who, col, target, got);
else break;
}
};
int g = 0;
for (int x : comp) if (ans[x] == ord[2]) {
dfs(dfs, x, c2, B, g);
assert(g == B);
break;
}
return ans;
}
for (int i = 0; i < n; i++) if (ap[i]) {
vector<vector<int>> nodes;
vector<bool> vis(n);
int cur = 0;
auto dfs = [&](auto&& s, int v) -> void {
nodes.back().push_back(v);
cur++, vis[v] = 1;
for (int u : adj[v]) if (!vis[u] && u != i) s(s, u);
};
int mx = 0;
for (int j : adj[i]) if (!vis[j]) {
cur = 0;
nodes.push_back({});
dfs(dfs, j);
ckmax(mx, cur);
}
for (const auto& comp : nodes) if (sz(comp) >= A && n - sz(comp) >= B) {
vector<int> ans(n, ord[2]);
int got2 = 0;
auto dfs3 = [&](auto&& s, int v) -> void {
if (got2 >= A) return;
got2++, ans[v] = c1;
for (int u : adj[v]) if (u != i && ans[u] == ord[2]) s(s, u);
};
dfs3(dfs3, comp[0]);
int got = 0;
auto dfs2 = [&](auto&& s, int v) -> void {
if (got >= B) return;
got++, ans[v] = c2;
for (int u : adj[v]) if (ans[u] == ord[2]) s(s, u);
};
dfs2(dfs2, i);
assert(got2 == A);
assert(got == B);
return ans;
}
}
return vector<int>(n);
}
