#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 = 2510;
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){
u = Find(u);
v = Find(v);
if(u == v) return ;
D[u].pb(v);
D[v].pb(u);
par[u] = v;
sz[v] += sz[u];
}
int SetD(int u, int cnt, int d){
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){
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);
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]);
memset(mk, 0, sizeof mk);
Build(0);
memset(mk, 0, sizeof mk);
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++)
for(auto adj : T[i])
if(adj != cen && i != cen && !fnd){
Unite(adj, i);
if(sz[Find(adj)] >= a){
fnd = true;
SetD(adj, a, ord[0]);
}
}
for(int i = 0; i < n; i++)
for(auto adj : G[i])
if(adj != cen && i != cen && !fnd){
Unite(adj, i);
if(sz[Find(adj)] >= a){
fnd = true;
SetD(adj, a, ord[0]);
}
}
// debug(cen);
// for(int i = 0; i < n; i++)
// cerr << Find(i) << ' ';
// cerr << '\n';
// cerr << "!! " << a << ' ' << b << ' ' << c << '\n';
// cerr << ord[0] << ord[1] << ord[2] << '\n';
if(!fnd)
return vector<int>(n, 0);
SetG(cen, b, ord[1]);
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;
}
