#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x.size())
#define fi first
#define se second
const int MX = (int)(1e5 +5);
typedef pair<int,int> ii;
vector<ii> vec[MX];
vector<int> res;
int A,B,C,c_a,c_b,c_c,cnt,N;
bool g;
int solve(int node,int p){
int ans=1;
for(auto &it:vec[node])
if(it.fi!=p){
if(it.se==-1)it.se=solve(it.fi,node);
ans+=it.se;
}
return ans;
}
void gimme(int node,int p,int o=0){
if(!cnt)return;
cnt--;
if(!o)res[node]=c_a;
else res[node]=c_b;
for(auto it:vec[node])
if(it.fi!=p && !res[it.fi])gimme(it.fi,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],-1});
vec[q[i]].push_back({p[i],-1});
}
//cerr<<solve(1,0)<<"\n";
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);
A=a,B=b,C=c;
//cerr<<A<<" "<<B<<" "<<C<<"\n";
for (int i = 0; i < n; ++i)
{
vector<ii> h;
int sum=1;
for(auto &it:vec[i]){
if(it.se==-1)it.se=solve(it.fi,i);
if((it.se>=B) && (n-it.se)>=A){
cnt=B,gimme(it.fi,i,1);
cnt=A,gimme(i,i);
g=1;
//exit(i);
break;
}
if((it.se>=A) && ((n-it.se)>=B)){
cnt=A,gimme(it.fi,i);
cnt=B,gimme(i,i,1);
g=1;
//exit(i);
break;
}
sum+=it.se;
}
if(g)break;
}
if(!g)return res;
for (int i = 0; i < n; ++i)
if(!res[i])res[i]=c_c;
return res;
}
