#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;
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;
}
vector<int> find_split(int n, int aa, int bb, int cc, vector<int> p, vector<int> q) {
N=n;
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);
}
if(a>b)
swap(a,b);
if(b>c)
swap(b,c);
if(a>b)
swap(a,b);
maketree(1);
/*
cout<<"STABLO"<<endl;
for(int i=1;i<=N;i++){
cout<<i<<": ";
for(int x:stablo[i])
cout<<x<<" ";
cout<<endl;
}*/
dfs1(1,1);
cent=findcentr(1,1);
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);
/* cout<<"ABC"<<endl;
for(int x:A)
cout<<x<<" ";
cout<<endl;
for(int x:B)
cout<<x<<" ";
cout<<endl;
for(int x:C)
cout<<x<<" ";
cout<<endl;
*/
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;
}
