#include "split.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 10;
vector<int> G[N], T[N], D[N];
int col[N];
int mk[N], sub[N];
void Build(int u){
mk[u] = 1;
sub[u] = 1;
for(auto adj : G[u]){
if(mk[adj]) continue;
T[u].pb(adj);
T[adj].pb(u);
Build(adj);
sub[u] += sub[adj];
}
}
int par[N], sz[N];
int Find(int u){
if(par[u] == u) return u;
return par[u] = Find(par[u]);
}
void Unite(int u, int v){
D[u].pb(v);
D[v].pb(u);
u = Find(u);
v = Find(v);
if(u == v) return ;
par[u] = v;
sz[v] += sz[u];
}
int SetD(int u, int cnt, int d){
assert(col[u] == 0);
if(cnt == 0) return 0;
cnt --;
col[u] = d;
for(auto adj : D[u]){
if(cnt == 0) return 0;
if(col[adj] == 0)
cnt = SetD(adj, cnt, d);
}
return cnt;
}
int SetG(int u, int cnt, int d){
assert(col[u] == 0);
if(cnt == 0) return 0;
cnt --;
col[u] = d;
for(auto adj : G[u]){
if(cnt == 0) return 0;
if(col[adj] == 0)
cnt = SetG(adj, cnt, d);
}
return cnt;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
fill(sz, sz + N, 1);
iota(par, par + N, 0);
for(int i = 0; i < N; i++)
G[i].clear(), T[i].clear(), D[i].clear();
int m = p.size();
for(int i = 0; i < m; i++)
G[p[i]].pb(q[i]), G[q[i]].pb(p[i]);
vector<int> ord = {1, 2, 3};
if(a > b) swap(a, b), swap(ord[0], ord[1]);
if(b > c) swap(b, c), swap(ord[2], ord[1]);
if(a > b) swap(a, b), swap(ord[0], ord[1]);
assert(a <= b);
assert(b <= c);
assert(a + b + c == n);
memset(mk, 0, sizeof mk);
Build(0);
memset(mk, 0, sizeof mk);
assert(sub[0] == n);
bool fnd = false;
int cen = 0;
while(!fnd){
fnd = true;
for(auto adj : T[cen]){
if(sub[adj] < sub[cen] && sub[adj] + sub[adj] > n){
fnd = false;
cen = adj;
break;
}
}
}
fnd = false;
for(int i = 0; i < n; i++){
if((i != cen) && (!fnd)){
// cerr << adj << "->" << i << '\n';
if(sz[Find(i)] >= a){
fnd = true;
int rem = SetD(i, a, ord[0]);
assert(rem == 0);
}
}
}
// for(int i = 0; i < m; i++){
// if((p[i] != cen) && (q[i] != cen) && (!fnd)){
// // cerr << "!! " << p[i] << ' ' << q[i] << '\n';
// Unite(p[i], q[i]);
// if(sz[Find(p[i])] >= a){
// fnd = true;
// int rem = SetD(p[i], a, ord[0]);
// assert(rem == 0);
// }
// }
// }
for(int i = 0; i < n; i++){
for(auto adj : T[i]){
if((adj != cen) && (i != cen) && (!fnd)){
// cerr << adj << "->" << i << '\n';
Unite(adj, i);
if(sz[Find(adj)] >= a){
fnd = true;
int rem = SetD(adj, a, ord[0]);
assert(rem == 0);
}
}
}
}
for(int i = 0; i < n; i++){
for(auto adj : G[i]){
if((adj != cen) && (i != cen) && (!fnd)){
// cerr << adj << "->" << i << '\n';
Unite(adj, i);
if(sz[Find(adj)] >= a){
fnd = true;
int rem = SetD(adj, a, ord[0]);
assert(rem == 0);
}
}
}
}
// debug(cen);
// for(int i = 0; i < n; i++)
// cerr << sz[Find(i)] << ' ';
// cerr << '\n';
// cerr << "!! " << a << ' ' << b << ' ' << c << '\n';
// cerr << ord[0] << ord[1] << ord[2] << '\n';
if(!fnd)
return vector<int>(n, 0);
int rem = SetG(cen, b, ord[1]);
assert(rem == 0);
for(int i = 0; i < n; i++) if(col[i] == 0) col[i] = ord[2];
vector<int> res;
for(int i = 0; i < n; i++)
res.pb(col[i]);
return res;
}
