#include "split.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
struct fnu{
vector<int> r;
fnu(int n){
r.resize(n);
REP(i, n) r[i] = i;
}
int f(int x){
if(r[x] != x) r[x] = f(r[x]);
return r[x];
}
void u(int a, int b){
a = f(a), b = f(b), r[a] = b;
}
};
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
vector<int> kolor = {1, 2, 3};
if(b > c) swap(b, c), swap(kolor[1], kolor[2]);
if(a > b) swap(a, b), swap(kolor[0], kolor[1]);
if(b > c) swap(b, c), swap(kolor[1], kolor[2]);
int m = ssize(p);
vector<vector<pii>> g(n);
REP(i, m){
int a = p[i], b = q[i];
g[a].emplace_back(b, i);
g[b].emplace_back(a, i);
}
fnu janusz(m);
vector<int> odw(n, 0), gl(n, 0), low(n, -1);
function<void(int, int)> dfs = [&](int w, int id_o){
odw[w] = 1;
low[w] = gl[w];
for(pii i : g[w]) if(i.se != id_o){
if(!odw[i.fi]){
gl[i.fi] = gl[w]+1;
dfs(i.fi, i.se);
if(low[i.fi] < gl[w]) janusz.u(id_o, i.se);
low[w] = min(low[w], low[i.fi]);
}
else if(gl[i.fi] < gl[w]){
janusz.u(id_o, i.se);
low[w] = min(low[w], gl[i.fi]);
}
}
};
dfs(0, -1);
int it = 0;
vector<int> skal(m, -1);
vector<int> spojna(m);
REP(i, m){
int t = janusz.f(i);
if(skal[t] < 0) skal[t] = it++;
spojna[i] = skal[t];
}
//~ REP(i, m) printf("%d: %d\n", i, spojna[i]);
vector<vector<int>> sklad(it);
vector<vector<int>> drz(it);
vector<int> waga(it, 0);
REP(w, n){
set<int> sas;
for(pii i : g[w]) sas.emplace(spojna[i.se]);
if(ssize(sas) == 1){
sklad[*sas.begin()].emplace_back(w);
++waga[*sas.begin()];
continue;
}
sklad.push_back({w});
waga.emplace_back(1);
drz.emplace_back();
for(int x : sas){
drz[it].emplace_back(x);
drz[x].emplace_back(it);
}
++it;
}
//~ printf("it: %d\n", it);
//~ REP(i, it){
//~ printf("%d: ", i);
//~ for(int x : sklad[i]) printf("%d ", x);
//~ printf("\n");
//~ }
//~ printf("drz:\n");
//~ REP(i, it){
//~ printf("%d: ", i);
//~ for(int x : drz[i]) printf("%d ", x);
//~ printf("\n");
//~ }
vector pdd = waga;
vector<int> oj(it);
function<void(int, int)> dfs_pdd = [&](int w, int o){
oj[w] = o;
for(int i : drz[w]) if(i != o) dfs_pdd(i, w), pdd[w] += pdd[i];
};
dfs_pdd(0, -1);
REP(xd, 2){
int ktory = -1;
REP(i, it) if(pdd[i] >= a){
if(n-pdd[i] >= b){
ktory = i;
break;
}
}
if(ktory >= 0){
vector czy(n, 0);
function<void(int)> dfs_odzyskaj = [&](int w){
for(int x : sklad[w]) czy[x] = 1;
for(int i : drz[w]) if(i != oj[w]) dfs_odzyskaj(i);
};
dfs_odzyskaj(ktory);
//~ REP(i, n) if(czy[i]) printf("czy: %d\n", i);
vector ret(n, kolor[2]);
function<void(int)> dfs_pomaluj_a = [&](int w){
//~ printf("a: %d\n", w);
if(!a) return;
ret[w] = kolor[0], --a;
for(auto [i, jajco] : g[w]) if(czy[i] && ret[i] == kolor[2]) dfs_pomaluj_a(i);
};
function<void(int)> dfs_pomaluj_b = [&](int w){
//~ printf("b: %d\n", w);
if(!b) return;
ret[w] = kolor[1], --b;
for(auto [i, jajco] : g[w]) if(!czy[i] && ret[i] == kolor[2]) dfs_pomaluj_b(i);
};
REP(i, n) if(czy[i]){dfs_pomaluj_a(i); break;}
REP(i, n) if(!czy[i]){dfs_pomaluj_b(i); break;}
return ret;
}
swap(a, b);
swap(kolor[0], kolor[1]);
}
return vector(n, 0);
}
