#include "split.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> ss, sz, pp, tin, low, st, res; int curt = 1;
vector<vector<int>> scc, adj;
void dfs(int v, int p) {
low[v] = tin[v] = curt++; pp[v] = p;
st.push_back(v);
for (auto& x : adj[v]) {
if (tin[x]) low[v] = min(low[v], tin[x]);
else {
dfs(x, v);
if (low[x] == tin[v]) {
scc.push_back({});
while (st.back() != v) { scc.back().push_back(st.back()); st.pop_back(); }
scc.back().push_back(v);
}
low[v] = min(low[v], low[x]);
}
}
}
int dfs_fill(int v, int t, int amt) {
if (!amt || res[v]) return amt;
res[v] = t; amt--;
for (auto& x : adj[v]) amt = dfs_fill(v, t, amt);
return amt;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int na = 1, nb = 2, nc = 3;
if (a > b) {
swap(a, b); swap(na, nb);
}
if (b > c) {
swap(b, c); swap(nb, nc);
}
if (a > b) {
swap(a, b); swap(nb, nc);//haha o(n) sorting OwO
}
sz = pp = tin = low = ss = res = vector<int>(n, 0);
adj.assign(n, {});
scc.clear();
int m = p.size();
for (int i = 0; i < m; i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
dfs(0, 0);
int mxv = 0, mxi = 0;
assert(scc.size());
for (int i = 0; i < scc.size(); i++) {
{
int mxsz = 0;
for (auto& x : scc[i]) {
mxsz = max(mxsz, sz[x]);
ss[x] = 0;
}
for (auto& x : scc[i]) {
ss[x] += sz[x]; ss[pp[x]] -= sz[x];
if (sz[x] == mxsz) ss[x] += n - sz[x];
}
for (auto& x : scc[i]) {
if (ss[x] >= n / 3) {
if (n - ss[x] > mxv) {
mxv = n - ss[x]; mxi = i;
goto end;
}
}
}
mxv = n / 3;mxi = i;
}
end:;
}
if (mxv < a) return res;
vector<int> mark1(n, 0);
int mxsz = 0;
for (auto& x : scc[mxi]) {
mark1[x] = 1;
mxsz = max(mxsz, sz[x]);
ss[x] = 0;
}
for (auto& x : scc[mxi]) {
ss[x] += sz[x]; ss[pp[x]] -= sz[x];
if (sz[x] == mxsz) ss[x] += n - sz[x];
}
for (auto& x : scc[mxi]) {
if (ss[x] >= n / 3) {
res[x] = nb; b--;
for (auto& x : adj[x])
if (!mark1[x])
b = dfs_fill(x, nb, b);
for (auto& x : scc[mxi])
if (!res[x])
a = dfs_fill(x, na, a);
goto end2;
}
}
end2:;
for (auto& x : res)if (!x)x = nc;
return res;
}
