#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
// sorry i hate globals
// but i will troll you with this
#define try kkwazzawazzakkwaquikkwalaquaza168zzabolazza
#define catch uvuvwevwevweonyetenyevweugwemubwemosas
vector<int> find_split(int N, int A, int B, int C, vector<int> U, vector<int> V) {
int M = U.size();
vector<int> T = {A, B, C};
vector<int> o(3);
iota(o.begin(), o.end(), 0);
sort(o.begin(), o.end(), [&](int i, int j) {
return T[i] < T[j];
});
vector<vector<int>> graph(N);
for (int i = 0; i < M; i++) {
graph[U[i]].push_back(V[i]);
graph[V[i]].push_back(U[i]);
}
// find spanning tree
vector<bool> vis(N);
vector<vector<int>> tree(N);
auto try = [&](auto &&try, int u) -> void {
vis[u] = true;
for (auto &v : graph[u]) {
if (!vis[v]) {
tree[u].push_back(v);
tree[v].push_back(u);
try(try, v);
}
}
};
try(try, 0);
// find centroid of tree
// also wow it discreetly became DSU ?!
bool found = false;
int cent = 0;
vector<int> sz(N, 1), par(N);
iota(par.begin(), par.end(), 0);
auto catch = [&](auto catch, int u, int p, int h) -> void {
par[u] = h;
for (auto &v : tree[u]) {
if (v != p) {
if (u == cent) h = v;
catch(catch, v, u, h);
sz[u] += sz[v];
}
}
if (!found and sz[u] * 2 >= N) {
found = true;
cent = u;
}
};
catch(catch, cent, -1, cent);
// find subtree sizes
unordered_set<int> leads;
sz.assign(N, 1);
// sneaky golem in the pocket
// i'm currently listening to peltorator explain FFT
// will this be useful to me? probably not in the near future
// am i entertained? yes, i subscribed (not paid to say this i swear)
// (also wow did you see that? i reused the FUNC.)
catch(catch, cent, -1, cent);
// casework:
// if we have a subtree of sz >= a (recall subtree size is now maxed by n/2)
// then we can assign all of this to a, and the rest to b
// if we don't then all sz < a, keep connecting via the original graph
// until we get a sz >= a, then assign the rest to b
int oth = -1;
for (auto &v : tree[cent]) {
if (sz[v] >= T[o[0]]) {
oth = v;
break;
}
}
auto find = [&](auto &&find, int u) -> int {
if (u == par[u]) return u;
return par[u] = find(find, par[u]);
};
auto unite = [&](int u, int v) -> int {
u = find(find, u), v = find(find, v);
if (u == v) return u;
if (sz[u] < sz[v]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
return u;
};
if (oth == -1) {
for (int i = 0; i < M; i++) {
int u = find(find, U[i]);
int v = find(find, V[i]);
if (u == cent or v == cent) continue;
int w = unite(u, v);
if (sz[w] >= T[o[0]]) {
oth = w;
break;
}
}
}
vector<int> res(N);
if (oth != -1) {
res.assign(N, o[1]+1);
bool set = false;
for (int i = 0; i < N; i++) {
int u = find(find, i);
if (u == oth) {
res[i] = o[0]+1;
} else if (!set) {
set = true;
res[i] = o[2]+1;
}
}
}
return res;
}
