#include "split.h"
#include <bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define sz(s) int(s.size())
#define pb push_back
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
//typedef pair<int,int> ii;
const ll MAX=1e5+5;
using namespace std;
vector<int> gfo[MAX];
vector<pair<ll,ll>> ord;
int tam[MAX], m[MAX];
int a, b, c, n;
bool xd=false;
void dfstams(int u, int f){
for(auto v:gfo[u]){
if(v!=f){
dfstams(v,u);
tam[u]+=tam[v];
}
}
tam[u]++;
return;
}
int cont;
void dfs(int u, int f, int marc){
if(cont==ord[marc].ff)return;
m[u]=ord[marc].ss;
cont++;
if(cont==ord[marc].ff)return;
for(auto v:gfo[u]){
if(v!=f){
dfs(v,u,marc);
}
}
}
bool lock(int u, int v){//arista
ll q=n-tam[u];
ll p=tam[u];
cont=0;
if(p>=ord[0].ff && q>=ord[1].ff){
dfs(u, v,0);
if(cont < ord[0].ff)return false;
cont=0;
dfs(v, u, 1);
if(cont < ord[1].ff)return false;
xd=true;
return true;
}
return false;
}
vector<int> find_split(int N, int A, int B, int C, vector<int> u, vector<int> v) {
a=A;
b=B;
c=C;
n=N;
ord.pb({a,1});
ord.pb({b,2});
ord.pb({c,3});
sort(all(ord));
vector<int> res;
for(int i=0; i<sz(u); i++){
gfo[u[i]].pb(v[i]);
gfo[v[i]].pb(u[i]);
}
dfstams(0, 0);
for(int i=0; i<n; i++){
for(auto v:gfo[i]){
if(lock(i,v))break;
}
if(xd)break;
}
for(int i=0; i<n; i++){
if(xd && m[i]==0){
m[i]=3;
}
}
for(int i=0; i<n; i++){
res.pb(m[i]);
}
return res;
}
/*
9 8
2 3 4
0 1
0 7
0 2
1 6
1 3
2 5
2 8
2 4
8 7
2 3 3
0 1
1 2
1 7
1 3
3 4
4 5
4 6
*/
