#include "split.h"
#include "bits/stdc++.h"
using namespace std;
#define vi vector<int>
#define ii pair<int,int>
const int mxn=1e5+5;
vi adj[mxn];
vi tam,res;
int act;
void init(int u, int pa){
tam[u]=1;
for(int v: adj[u]) if(v!=pa){
init(v,u);
tam[u]+=tam[v];
}
}
void paint(int u, int pa, int cant, int col){
if(act>=cant) return;
res[u]=col,act++;
for(int v: adj[u])
if(v!=pa) paint(v,u,cant,col);
}
vi find_split(int n, int a, int b, int c, vi p, vi q) {
int m=(int)p.size();
if(m!=n-1) return vi (n,0);
for(int i=0;i<m;i++)
adj[p[i]].push_back(q[i]),adj[q[i]].push_back(p[i]);
tam.resize(n);
init(0,-1);
ii col[3]={{a,1},
{b,2},
{c,3}};
sort(col,col+3);
res.assign(n,col[2].second);
bool found=false;
for(int i=0;i<m;i++){
int u=p[i],v=q[i];
if(tam[u]<tam[v]) swap(u,v);
int x=n-tam[v],y=tam[v];
if(x>y) swap(u,v),swap(x,y);
if(x<col[0].first || y<col[1].first) continue;
act=0;
paint(u,v,col[0].first,col[0].second);
act=0;
paint(v,u,col[1].first,col[1].second);
found=true;
break;
}
return found ? res : vi (n,0);
}
