#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x.size())
const int MX = (int)(1e5+5);
vector<int> vec[MX],res;
int s[MX],A,B,C,c_a,c_b,c_c,cnt;
void dfs(int node,int p){
s[node]=1;
for(auto it:vec[node])
if(it!=p)dfs(it,node),s[node]+=s[it];
}
bool comp(int a,int b){
if(s[a]!=s[b])return s[a]>s[b];
return a<b;
}
int solve(int node,int p){
//cerr<<node<<" , ";
//cerr<<sz(vec[node])<<"\n";
vector<int> g;
for(auto it:vec[node])
if(it!=p)g.push_back(it);
sort(g.begin(),g.end(),comp);
if(A==1 && sz(g)>=1 && s[g[0]]>=B)return node;
if(sz(g)>=2){
if(s[g[0]]>=B && (s[g[1]]+1)>=A)
return node;
return solve(g[0],node);
}
if(sz(g)>=1)return solve(g[0],node);
return -1;
}
void gimme(int node,int p,int o=0){
if(!cnt)return;
cnt--;
//cerr<<node<<" "<<o<<"\n";
if(!o)res[node]=c_a;
else res[node]=c_b;
for(auto it:vec[node])
if(it!=p)gimme(it,node,o);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
res.resize(n);
fill(res.begin(),res.end(),0);
for (int i = 0; i < n-1; ++i)
{
vec[p[i]].push_back(q[i]);
vec[q[i]].push_back(p[i]);
}
dfs(0,0);
c_a=1,c_b=2,c_c=3;
if(a>b)swap(a,b),swap(c_a,c_b);
if(a>c)swap(a,c),swap(c_a,c_c);
if(b>c)swap(b,c),swap(c_b,c_c);
/*cerr<<a<<" "<<b<<" "<<c<<"\n";
cerr<<c_a<<" "<<c_b<<" "<<c_c<<"\n";*/
A=a,B=b,C=c;
int idx=solve(0,0);
if(idx==-1)
return res;
//cerr<<idx<<"\n";
res[idx]=c_a;
dfs(idx,idx);
sort(vec[idx].begin(),vec[idx].end(),comp);
if(a!=1)cnt=a-1,gimme(vec[idx][1],idx);
cnt=b,gimme(vec[idx][0],idx,1);
for (int i = 0; i < n; ++i)
if(!res[i])res[i]=c_c;
return res;
}
