#include "split.h"
#include <bits/stdc++.h>
using namespace std;
int N,A,B,C,node=-1;
vector<int> subtree,ans;
vector<vector<int>> edges;
void run(int u,int par,int tmp){
if(tmp==1){
if(A>0){
ans[u]=1;
A--;
}else{
ans[u]=3;
}
}else if(tmp==2){
if(B>0){
ans[u]=2;
B--;
}else{
ans[u]=3;
}
}
for(auto v:edges[u]){
if(v!=par&&v!=node){
run(v,u,tmp);
}
}
}
void dfs(int u,int par){
// cout << u << ' ' << par << '\n';
for(auto v:edges[u]){
if(v!=par){
dfs(v,u);
subtree[u]+=subtree[v];
// cout << v << ' ' << subtree[v] << '\n';
if(subtree[v]>=A&&N-subtree[v]>=B&&node==-1){
node=v;
run(v,u,1);
}
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m=p.size();
if(b<a){
swap(a,b);
}
if(c<a){
swap(a,c);
}
if(c<b){
swap(b,c);
}
A=a;B=b;C=c;N=n;
edges.resize(n);subtree.resize(n,1);ans.resize(n,0);
for(int i=0;i<m;i++){
edges[p[i]].push_back(q[i]);
edges[q[i]].push_back(p[i]);
}
if(m==n-1){
dfs(0,-1);
if(node!=-1){
run(0,-1,2);
}
}
return ans;
}
