#include "split.h"
#include <bits/stdc++.h>
#define sc second
#define ff first
using namespace std;
typedef pair<int,int> ii;
vector<vector<int>> G;
vector<int> A;
vector<int> B;
vector<int> C;
int vis[100010];
void dfs(int node,int a,int b,int c){
vis[node]=1;
B.push_back(node);
if(B.size()==b)return;
for(auto i:G[node]){
if(vis[i]==-1){
dfs(i,a,b,c);
if(B.size()==b)return;
}
}
}
void dfs2(int node,int a,int b,int c){
//cout<<node<<endl;
if(A.size()<a){
A.push_back(node);
}
else{
if(B.size()<b){
B.push_back(node);
}
else{
C.push_back(node);
}
}
vis[node]=1;
for(auto i:G[node]){
//cout<<i<<" ";
if(vis[i]==-1){
dfs2(i,a,b,c);
}
}
//cout<<endl;
}
int sz[100010];
int N;
int dfsz(int node,int pad){
sz[node]=1;
vis[node]=1;
for(auto i:G[node]){
if(vis[i]!=-1)continue;
sz[node]+=dfsz(i,node);
}
return sz[node];
}
int piv=-1,an=-1;
vector<int> ans;
void dfsfind(int node,int pad,int a,int b){
//cout<<node<<" "<<sz[node]<<endl;
vis[node]=1;
if(sz[node]>=a && N-sz[node]>=b){
piv=node;an=pad;
return;
}
if(sz[node]>=b && N-sz[node]>=a){
piv=pad;an=node;
return;
}
for(auto i:G[node]){
if(vis[i]!=-1)continue;
dfsfind(i,node,a,b);
}
}
int cnt=0;
void dfs1(int node,int pad,int a,int col){
cnt++;
vis[pad]=1;
vis[node]=1;
if(cnt<=a){
ans[node]=col;
}
for(auto i:G[node]){
if(vis[i]!=-1)continue;
dfs1(i,node,a,col);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N=n;
ans.assign(n,0);
vector<ii> v{ii(a,1),ii(b,2),ii(c,3)};
sort(v.begin(),v.end());
G.assign(n+5,vector<int>());
for(int i=0;i<p.size();i++){
G[p[i]].push_back(q[i]);
G[q[i]].push_back(p[i]);
}
memset(vis,-1,sizeof vis);
int h=dfsz(0,0);
memset(vis,-1,sizeof vis);
dfsfind(0,0,v[0].ff,v[1].ff);
if(piv==-1 && an==-1)return ans;
cnt=0;
//cout<<piv<<" "<<an<<endl;
memset(vis,-1,sizeof vis);
dfs1(piv,an,v[0].ff,v[0].sc);
memset(vis,-1,sizeof vis);
cnt=0;
dfs1(an,piv,v[1].ff,v[1].sc);
for(int i=0;i<n;i++){
if(ans[i]==0){
ans[i]=v[2].sc;
}}
return ans;
}
