#include "split.h"
#include <bits/stdc++.h>
using namespace std;
int N,node=-1;
bool useA;
pair<int,int> A,B,C;
vector<int> subtree,ans;
vector<vector<int>> edges;
void run(int u,int par,int tmp){
if(tmp==1){
if(A.first>0){
ans[u]=A.second;
A.first--;
}else{
return;
}
}else if(tmp==2){
if(B.first>0){
ans[u]=B.second;
B.first--;
}else{
return;
}
}
for(auto v:edges[u]){
if(v!=par&&v!=node&&ans[v]==0){
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.first&&N-subtree[v]>=B.first&&node==-1){
node=v;
useA=true;
run(v,u,1);
}else if(subtree[v]>=B.first&&N-subtree[v]>=A.first&&node==-1){
node=v;
useA=false;
run(v,u,2);
}
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m=p.size();
A={a,1};B={b,2};C={c,3};N=n;
if(B<A){
swap(A,B);
}
if(C<A){
swap(A,C);
}
if(C<B){
swap(B,C);
}
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){
if(useA){
run(0,-1,2);
}else{
run(0,-1,1);
}
for(int i=0;i<n;i++){
if(ans[i]==0){
ans[i]=C.second;
}
}
}
}else{
run(0,-1,1);
for(int i=0;i<n;i++){
if(ans[i]==0){
run(i,-1,2);
break;
}
}
for(int i=0;i<n;i++){
if(ans[i]==0){
ans[i]=C.second;
}
}
}
return ans;
}
