#include "split.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
ll N,a,b,c,siz[maxn],cent;
bool prosli[maxn],blok[maxn];
vector<int> graf[maxn],stablo[maxn],A,B,C,V,res;
mt19937_64 rng;
bool podeg(int a,int b){
return graf[a].size()<graf[b].size();
}
int perm[maxn];
void maketree(int gde){
prosli[gde]=true;
for(int p:graf[gde])
if(!prosli[p]){
stablo[gde].push_back(p);
stablo[p].push_back(gde);
maketree(p);
}
}
int dfs1(int gde,int pret){
siz[gde]=1;
for(int p:stablo[gde])
if(p!=pret)
siz[gde]+=dfs1(p,gde);
return siz[gde];
}
int findcentr(int gde,int pret){
for(int p:stablo[gde]){
if(p==pret)
continue;
if(siz[p]>=N/2+1)
return findcentr(p,gde);
}
return gde;
}
int collect(int gde,int pret,int kol){
if(kol==0)
return 0;
//cout<<"COLLECT "<<gde<<" "<<kol<<endl;
V.push_back(gde);
int ret=1;
kol--;
for(int p:stablo[gde]){
if(p==pret)
continue;
if(blok[p])
continue;
int v=collect(p,gde,kol);
kol-=v;
ret+=v;
if(kol==0)
return ret;
}
return ret;
}
void reset(){
for(int i=1;i<=N;i++){
siz[i]=0;
prosli[i]=false;
blok[i]=false;
stablo[i].clear();
}
A.clear();
B.clear();
C.clear();
V.clear();
}
vector<int> find_split(int n, int aa, int bb, int cc, vector<int> p, vector<int> q) {
rng.seed(1525);
N=n;
for(int i=1;i<=N;i++)
perm[i]=i;
for(int i=2;i<=N;i++)
swap(perm[i],perm[rng()%i+1]);
for(int i=1;i<=N;i++)
res.push_back(0);
a=aa;
b=bb;
c=cc;
for(int i=0;i<p.size();i++){
int x=p[i];
int y=q[i];
x++;
y++;
graf[x].push_back(y);
graf[y].push_back(x);
}
for(int i=1;i<=N;i++)
sort(graf[i].begin(),graf[i].end(),podeg);
if(a>b)
swap(a,b);
if(b>c)
swap(b,c);
if(a>b)
swap(a,b);
int maxit=N;
if(N>2500)
maxit=200;
for(int it=1;it<=maxit;it++){
int x=perm[it];
//cout<<x<<endl;
reset();
maketree(x);
dfs1(x,x);
cent=findcentr(x,x);
dfs1(cent,cent);
int koji=-1;
for(int x:stablo[cent])
if(siz[x]>=a)
koji=x;
if(koji!=-1){
blok[cent]=true;
collect(koji,koji,a);
A=V;
V.clear();
blok[cent]=false;
blok[koji]=true;
collect(cent,cent,b);
B=V;
for(int i=1;i<=N;i++)
prosli[i]=false;
for(int x:A)
prosli[x]=true;
for(int x:B)
prosli[x]=true;
for(int i=1;i<=N;i++)
if(prosli[i]==false)
C.push_back(i);
if(aa==B.size())
swap(A,B);
if(aa==C.size())
swap(A,C);
if(bb==C.size())
swap(B,C);
for(int x:A)
res[x-1]=1;
for(int x:B)
res[x-1]=2;
for(int x:C)
res[x-1]=3;
return res;
}
}
return res;
}
