#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int SZ = 2e5 + 5;
vector <int> vg[SZ], va[SZ];
int n;
int d[SZ], Max[SZ];
bool viz[SZ];
void dfs(int nod){
viz[nod] = 1; d[nod] = 1;
for(auto it : vg[nod]){
if(viz[it]) continue ;
va[it].push_back(nod);
va[nod].push_back(it);
dfs(it);
d[nod] += d[it];
Max[nod] = max(Max[nod], d[it]);
}
}
int find_centroid(int nod){
viz[nod] = 1;
if(max(Max[nod], n - d[nod]) <= n / 2) return nod;
for(auto it : va[nod]){
if(viz[it]) continue ;
int x = find_centroid(it);
if(x) return x;
}
return 0;
}
vector <int> comp[SZ];
int id[SZ], RG[SZ];
inline int find(int x){
int R = x;
while(R != id[R]) R = id[R];
while(id[x] != R){
int aux = id[x];
id[x] = R;
x = aux;
}
return R;
}
inline void unite(int x, int y){
if(x == y) return ;
if(RG[x] >= RG[y]) id[y] = x, RG[x] += RG[y];
else id[x] = y, RG[y] += RG[x];
}
void make_comp(int nod, int NR){
comp[NR].push_back(nod);
viz[nod] = 1;
for(auto it : va[nod]){
if(viz[it]) continue ;
unite(find(it), find(nod));
make_comp(it, NR);
}
}
void merge_comp(int nod, int &am, int a){
if(am >= a) return ;
viz[nod] = 1;
for(auto it : vg[nod]){
if(viz[it]) continue ;
if(find(it) == find(nod)) merge_comp(it, am, a);
else{
unite(find(nod), find(it));
am = RG[find(nod)];
if(am >= a) return ;
merge_comp(it, am, a);
}
}
return ;
}
int cul[SZ];
int rem;
void paint_comp(int nod, int c){
if(rem == 0) return ;
viz[nod] = 1;
--rem;
cul[nod] = c;
for(auto it : vg[nod]){
if(viz[it] || cul[it] || find(it) != find(nod)) continue ;
if(rem) paint_comp(it, c);
}
}
vector<int> res;
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n = N;
res.resize(n);
int m = p.size();
for(int i = 0; i < m ; ++i){
vg[p[i] + 1].push_back(q[i] + 1);
vg[q[i] + 1].push_back(p[i] + 1);
}
int ca = 1, cb = 2, cc = 3;
if(a > b) swap(a, b), swap(ca, cb);
if(a > c) swap(a, c), swap(ca, cc);
if(b > c) swap(b, c), swap(cb, cc);
for(int i = 1; i <= n ; ++i) id[i] = i, RG[i] = 1;
dfs(1);
memset(viz, 0, sizeof(viz));
int nod = find_centroid(1);
memset(viz, 0, sizeof(viz));
int NR = 0;
viz[nod] = 1;
for(auto it : va[nod]){
make_comp(it, NR);
NR++;
}
bool found = false;
int wh = 0;
for(int i = 0; i < NR ; ++i){
if(comp[i].size() >= a){
found = true;
wh = comp[i][0];
break ;
}
}
//cerr << found << endl;
if(!found){
memset(viz, 0, sizeof(viz));
viz[nod] = 1;
for(int i = 0; i < NR ; ++i){
int x = RG[find(comp[i][0])];
merge_comp(comp[i][0], x, a);
if(x >= a){
wh = comp[i][0];
break ;
}
}
}
if(wh == 0) return res;
memset(viz, 0, sizeof(viz));
viz[nod] = 1;
rem = a;
paint_comp(wh, ca);
for(int i = 1; i <= n ; ++i) unite(find(i), find(nod));
memset(viz, 0, sizeof(viz));
rem = b;
paint_comp(nod, cb);
for(int i = 0; i < n ; ++i){
if(cul[i + 1] == 0) cul[i + 1] = cc;
res[i] = cul[i + 1];
}
return res;
}
