#pragma GCC optimize("unroll-loops")
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5+5;
int n, m;
vector<int> edges[MAXN];
// vector<int> tree[MAXN];
// pii elist[2*MAXN];
vector<int> res;
// bool vis[MAXN];
// int sz[MAXN];
bool is_point[MAXN];
int lp[MAXN];
int depth[MAXN];
bool vis[MAXN];
bool cut[MAXN];
int to_bcc[MAXN];
int sz[MAXN];
vector<int> stck;
vector<vector<int>> bccs;
bool tested[MAXN];
bool fin[MAXN];
bool vis2[MAXN];
void bcc(int cur, int p = -1) {
stck.push_back(cur);
vis[cur] = 1;
int num = 0;
for (int nxt: edges[cur]) {
if (nxt == p) continue;
if (vis[nxt]) {
if (depth[nxt] < depth[lp[cur]]) lp[cur] = nxt;
continue;
}
depth[nxt] = 1+depth[cur];
bcc(nxt, cur);
if ((depth[lp[nxt]] >= depth[cur] && cur != 0) || (cur == 0 && num)) {
cut[cur] = 1;
int p;
vector<int> v;
do {
p = stck.back();
stck.pop_back();
v.push_back(p);
to_bcc[p] = bccs.size();
} while (p != nxt);
v.push_back(cur);
to_bcc[cur] = bccs.size();
bccs.push_back(v);
}
if (depth[lp[nxt]] < depth[lp[cur]]) lp[cur] = lp[nxt];
num++;
}
if (cur == 0) {
vector<int> v;
while (!stck.empty()) {
int p = stck.back();
stck.pop_back();
v.push_back(p);
to_bcc[p] = bccs.size();
}
bccs.push_back(v);
}
}
bool cut2[MAXN];
void get_cut(int cur, int p = -1) {
vis2[cur] = 1;
int num = 0;
for (int nxt: edges[cur]) {
if (nxt == p || fin[nxt]) continue;
if (vis2[nxt]) {
if (depth[nxt] < depth[lp[cur]]) lp[cur] = nxt;
continue;
}
depth[nxt] = 1+depth[cur];
get_cut(nxt, cur);
if ((depth[lp[nxt]] >= depth[cur] && cur != 0) || (cur == 0 && num)) {
cut[cur] = 1;
}
if (depth[lp[nxt]] < depth[lp[cur]]) lp[cur] = lp[nxt];
num++;
}
}
void set_up(int cur) {
iota(lp, lp+n, 0);
fill(depth, depth+n, 0);
fill(cut2, cut2+n, 0);
fill(vis2, vis2+n, 0);
get_cut(cur);
}
void dfs(int cur) {
vis[cur] = 1;
sz[cur] = 1;
for (int nxt: edges[cur]) {
if (vis[nxt]) continue;
dfs(nxt);
sz[cur] += sz[nxt];
}
}
void assign(int cur, bool col, int &a) {
if (a == 0) return;
vis[cur] = 1;
res[cur] = col;
a--;
for (int nxt: edges[cur]) {
if (!vis[nxt]) {
assign(nxt, col, a);
}
}
}
bool test(int cur, int &a, int &b) {
vector<pii> szs;
fill(vis, vis+n, 0);
if (cut[cur]) { // therefore, this finds incorrect splits
// return 0;
vis[cur] = 1;
for (int nxt: edges[cur]) {
if (vis[nxt]) continue;
dfs(nxt);
szs.push_back(pii(sz[nxt], nxt));
}
fill(vis, vis+n, 0);
for (pii p: szs) {
vis[cur] = 1;
if (p.first >= a && n-p.first >= b) {
assign(p.first, 0, a);
vis[cur] = 0;
assign(cur, 1, b);
return 1;
}
if (p.first >= b && n-p.first >= a) {
assign(p.first, 1, b);
vis[cur] = 0;
assign(cur, 0, a);
return 1;
}
}
return 0;
}
else {
if (tested[cur]) return 0;
for (int v: bccs[to_bcc[cur]]) {
tested[v] = 1;
vis[v] = 1;
}
vector<pii> szs;
for (int v: bccs[to_bcc[cur]]) {
if (cut[v]) {
dfs(v);
szs.push_back(pii(sz[v], v));
}
}
szs.push_back(pii(0, -1));
sort(szs.begin(), szs.end());
// if the biggest thing is too big for b, return 0
if (n-szs.back().first < a) return 0;
// always possible otherwise
if (szs.back().first >= a) {
fill(vis, vis+n, 0);
for (int v: bccs[to_bcc[cur]]) {
vis[v] = 1;
}
bool ex = szs.back().first >= b;
assign(szs.back().second, ex, ex ? b : a);
for (int v: bccs[to_bcc[cur]]) {
vis[v] = 0;
}
vis[szs.back().second] = 1;
assign(cur, !ex, ex ? a : b);
}
else {
fill(fin, fin+n, 1);
for (int v: bccs[to_bcc[cur]]) fin[v] = 0;
// just add stuff until you exceed b
for (int v: bccs[to_bcc[cur]]) {
if (!cut[v]) sz[v] = 1;
}
set<int> adj;
adj.insert(cur);
fill(vis, vis+n, 0);
for (int v: bccs[to_bcc[cur]]) vis[v] = 1;
// for (int v: bccs[to_bcc[cur]]) cerr << v << ' ';
// cerr << endl;
while (b > 0) {
assert(!adj.empty());
set_up(*(adj.begin()));
int f = -1;
for (int v: adj) {
if (!cut2[v]) {
f = v;
break;
}
}
assert(f != -1);
assign(f, 1, b);
adj.erase(f);
fin[f] = 1;
for (int nxt: edges[f]) {
if (fin[nxt]) continue;
adj.insert(nxt);
}
}
assert(!adj.empty());
for (int i = 0; i < n; i++) vis[i] = (res[i] == 1);
assign(*(adj.begin()), 0, a);
assert(a == 0);
assert(b == 0);
}
// assert(false);
// cerr << "success\n";
return 1;
}
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n = N;
m = p.size();
vector<pii> change({{a, 1}, {b, 2}, {c, 3}});
sort(change.begin(), change.end());
a = change[0].first;
b = change[1].first;
for (int i = 0; i < m; i++) {
edges[p[i]].push_back(q[i]);
edges[q[i]].push_back(p[i]);
// elist[i] = pii(p[i], q[i]);
}
bool f = 0;
iota(lp, lp+n, 0);
bcc(0);
// fill(vis, vis+n, 0);
res = vector<int>(n, 2);
for (int i = 0; i < n; i++) {
if (test(i, a, b)) {
assert(a == 0);
assert(b == 0);
// cerr << i << '\n';
f = 1;
break;
}
}
if (f) for (int i = 0; i < n; i++) res[i] = change[res[i]].second;
else res = vector<int>(n, 0);
return res;
}
