#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) {
sz[v] = 1;
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); sz[v] += sz[x];
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(x, 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(na, nb);//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 mxi = -1;
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] = sz[x];
}
for (auto& x : scc[i]) {
if (x) ss[pp[x]] -= sz[x];
if (sz[x] == mxsz) ss[x] += n - sz[x];
}
int sm = 0;
for (auto& x : scc[i]) sm += ss[x];
assert(sm == n);
for (auto& x : scc[i]) {
if (ss[x] >= b) {
if (n - ss[x] >= a) {
mxi = i;
}
goto end;
}
}
mxi = i; break;
}
end:;
}
if (mxi == -1) return res;
vector<int> mark1(n, 0);
vector<int> mark2(n, 0);
vector<int> cntc(n, 0);
int mxsz = 0;
for (auto& x : scc[mxi]) {
mark1[x] = 1;
mxsz = max(mxsz, sz[x]);
ss[x] = sz[x];
}
for (auto& x : scc[mxi]) {
if (x) { ss[pp[x]] -= sz[x]; cntc[pp[x]]++; }
if (sz[x] == mxsz) ss[x] += n - sz[x];
}
for (auto& x : scc[mxi]) {
if (ss[x] >= b) {
res[x] = nb; b--;
for (auto& x : adj[x])
if (!mark1[x])
b = dfs_fill(x, nb, b);
assert(!b);
for (auto& x : scc[mxi])
if (!res[x])
a = dfs_fill(x, na, a);
//assert(!a);
goto end2;
}
}
vector<int> st;
for (auto& x : scc[mxi]) if (cntc[x] == 0) st.push_back(x);
while (st.size()) {
int c = st.back(); st.pop_back();
mark2[c]++;
if (ss[c] >= b) {
vector<int> q; q.push_back(c);
while (q.size()) {
int t = q.back(); q.pop_back();
mark2[t] = 0; res[t] = nb; b--;
for (auto& x : adj[t]) {
if (!mark1[x])
b = dfs_fill(x, nb, b);
if (mark2[x]) q.push_back(x);
}
if (!b) break;
}
for (auto& x : scc[mxi])
if (!res[x])
a = dfs_fill(x, na, a);
goto end2;
}
ss[pp[c]] += ss[c];
cntc[pp[c]]--;
if (!cntc[pp[c]]) st.push_back(pp[c]);
}
end2:;
for (auto& x : res)if (!x)x = nc;
return res;
}
