#include "split.h"
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using namespace std;
const int N=2e5+5;
int n,a,b,c,sz[N],tin[N],t,mn,tree[N],h[3]={1,2,3},bh;
vector<int> adj[N],v,ans,A,B,C;
pair<int,int> bs[N];
bool vis[N];
bool cmp(int x,int y){
int hx,hy;
if (x==1) hx=a;
if (x==2) hx=b;
if (x==3) hx=c;
if (y==1) hy=a;
if (y==2) hy=b;
if (y==3) hy=c;
return hx<hy;
}
int getsz(int x,int p){
sz[x]=1;
for (auto u:adj[x]) if (u!=p) sz[x]+=getsz(u,x);
return sz[x];
}
void dfs(int x,int p){
tin[x]=++t;
sz[x]=1;
tree[t]=x;
for (auto u:adj[x]){
if (u==p) continue;
dfs(u,x);
sz[u]+=sz[x];
}
return;
}
void getb(int x,int p){
bh--;
ans[x-1]=h[1];
if (!bh) return;
for (auto u:adj[x]){
if (u==p || ans[u-1]) continue;
getb(u,x);
}return;
}
vector<int> find_split(int NN,int aa,int bb,int cc,vector<int> Q,vector<int> P){
n=NN,a=aa,b=bb,c=cc;
mn=min(min(a,b),c);
for (int i=0;i<Q.size();i++){
int x=Q[i]+1,y=P[i]+1;
adj[x].pb(y);
adj[y].pb(x);
}
for (int i=0;i<n;i++) ans.pb(0);
getsz(1,0);
vector<int> best={n,1,1};
for (int i=1;i<=n;i++){
bs[i]={n,1};
if (sz[i]>=mn) bs[i]={sz[i],1};
for (auto u:adj[i]){
if (sz[u]>sz[i]) continue;
if (n-sz[u]>=mn) bs[i]=min(bs[i],{n-sz[u],u});
}
best=min(best,{bs[i].F,bs[i].S,i});
}
if (best[0]==n) return ans;
sort(h,h+3,cmp);
dfs(best[1],0);
for (int i=tin[best[2]];i<=tin[best[2]]+mn-1;i++) ans[tree[i]-1]=h[0];
if (h[1]==1) bh=a;
if (h[1]==2) bh=b;
if (h[1]==3) bh=c;
if (!ans[0]) getb(best[1],0);
for (int i=0;i<n;i++) if (!ans[i]) ans[i]=h[2];
for (int i=0;i<n;i++){
if (ans[i]==1) a--;
if (ans[i]==2) b--;
if (ans[i]==3) c--;
}
if (a || b || c){
for (int i=0;i<n;i++) ans[i]=0;
}
return ans;
}
