#include "split.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<int> vi;
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORi(i,b,n) for(int i=b;i<n;i++)
#define FOA(i,n) for(auto i : n)
#define len(a) ((int)a.size())
vector<vi> adj;
int ssub[1000000];
vi ans;
vi par;
int dfs(int s, int p=-1){
par[s] = p;
ssub[s] = 1;
for(auto v : adj[s]) if(v!=p) ssub[s]+=dfs(v, s);
return ssub[s];
}
int acnt=0;
int A;
void traveA(int s, int p=-1){
//cout<<s<<" "<<p<<endl;
//cout<<ans[s]<<endl;
////cout<<s<<" "<<p<<endl;
ans[s] = 1;
////cout<<s<<" "<<p<<endl;
acnt++;
////cout<<s<<" "<<p<<endl;
////cout<<adj[s].size()<<endl;
for(auto v : adj[s]) if(v!=p) traveA(v, s);
if(acnt>A) acnt--, ans[s] = 3;
}
int bcnt=0;
int B;
void traveB(int s, int p=-1){
//cout<<s<<" "<<p<<endl;
//cout<<ans[s]<<endl;
if(!ans[s]){
ans[s] = 2;
bcnt++;
}
for(auto v : adj[s]) if(v!=p) traveB(v, s);
if(bcnt>B && ans[s]==2) bcnt--, ans[s] = 3;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
A = a;
B = b;
adj.assign(n+1, vi());
ans.resize(n);
par.resize(n+1);
FOR(i,len(p)){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
dfs(1);
int mindiffpos=0, mindiff=1000000000;
FOR(i,n){
if(ssub[i+1]>a && ssub[i+1]<mindiff) mindiff = ssub[i+1], mindiffpos = i+1;
}
int mindiffb=100000000, mindiffposb=0;
FOR(i,n){
if(ssub[i+1]>b && ssub[i+1]<mindiffb) mindiffb = ssub[i+1], mindiffposb = i+1;
}
if(mindiff-a>mindiffb-b){
swap(a,b);
swap(mindiff,mindiffb);
swap(mindiffpos,mindiffposb);
}
int mindiffc=100000000, mindiffposc=0;
FOR(i,n){
if(ssub[i+1]>c && ssub[i+1]<mindiffc) mindiffc = ssub[i+1], mindiffposc = i+1;
}
if(mindiff-a>mindiffc-c){
swap(a,c);
swap(mindiff,mindiffc);
swap(mindiffpos,mindiffposc);
}
//cout<<mindiff<<" "<<mindiffpos<<endl;
traveA(mindiffpos, par[mindiffpos]);
traveB(1);
FOR(i,n){
if(ans[i]==2) b--;
else if(ans[i]==1) a--;
else c--;
//cout<<ans[i]<<" ";
}
//cout<<endl;
//cout<<a<<" "<<b<<" "<<c<<endl;
if(a || b || c){
ans.assign(n, 0);
}
return ans;
}
