#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]), dist(n, 1e9);
queue<int> q;
dist[comp[0]] = 0;
q.push(comp[0]);
int got = 0;
while (q.size()) {
int v = q.front(); q.pop();
ans[v] = c1;
if (++got == A) break;
for (int u : adj[v]) if (in[u] && ckmin(dist[u], dist[v] + 1)) {
q.push(u);
}
}
assert(got == A);
for (int x : comp) if (ans[x] == ord[2]) ans[x] = c2;
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 = 0; j < n; j++) if (i != j && !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]);
for (int x : comp) ans[x] = c1;
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);
return ans;
}
}
return vector<int>(n);
}
