#include<bits/stdc++.h>
#include "split.h"
using namespace std;
//asdasd
#define all(x) x.begin(), x.end()
#define pb push_back
#define ll long long
#define vout(v) for(int i=0; i<v.size(); i++) cout<<v[i]<<' '
#define pii pair<int, int>
#define ff first
#define ss second
#define mp make_pair
vector<int> q[200100];
int sz[200100];
int res[200100], p[200100];
void dfs1(int v){
sz[v] = 1;
for(int i=0; i<q[v].size(); i++){
int to = q[v][i];
if(to == p[v]) continue;
p[to] = v;
dfs1(to);
sz[v] += sz[to];
}
}
int dfs2(int v, int x, int c){
res[v] = c;
//cout<<v<<' '<<x<<'\n';
x--;
for(int i=0; i<q[v].size() and x != 0; i++){
int to = q[v][i];
if(p[v] == to) continue;
p[to] = v;
x = dfs2(to, x, c);
}
return x;
}
vector<int> find_split(int n, int A, int B, int C, vector<int> LL, vector<int> RR){
int m = LL.size();
if(n == m) m--;
for(int i=0; i<m; i++){
q[LL[i] + 1].pb(RR[i] + 1);
q[RR[i] + 1].pb(LL[i] + 1);
}
if(A == 1){
p[1] = 0;
dfs2(1, B, 2);
vector<int> ans(n);
for(int i=1; i<=n; i++){
if(res[i] == 0){
if(C){
C--;
res[i] = 3;
}
else{
res[i] = 1;
}
}
ans[i-1] = res[i];
}
return ans;
}
//cout<<"asdasdasdasd\n\n\n\n\n";
if(n == m+1){
p[1] = 0;
dfs1(1);
vector<pii> qq;
qq.pb(mp(A, 1));
qq.pb(mp(B, 2));
qq.pb(mp(C, 3));
sort(all(qq));
pii d1=qq[0], d2=qq[1];
int ok=0;
for(int i=2; i<=n; i++){
//cout<<sz[i]<<' ';
if(min(d1.ff, d2.ff) <= min(sz[i], n-sz[i]) and max(d1.ff, d2.ff) <= max(sz[i], n-sz[i])){
ok=i;
break;
}
}
vector<int> ans(n, 0);
//cout<<ok<<"\n\n\n\n";
if(!ok){
return ans;
}
int t = p[ok];
if(sz[ok] > n - sz[ok]){
p[ok] = t;
dfs2(ok, d2.ff, d2.ss);
p[t] = ok;
dfs2(t, d1.ff, d1.ss);
}
else{
//cout<<"asdsad";
p[ok] = t;
dfs2(ok, d1.ff, d1.ss);
p[t] = ok;
dfs2(t, d2.ff, d2.ss);
//cout<<d2.ff<<'\n';
}
for(int i=1; i<=n; i++){
if(res[i] == 0) res[i] = qq[2].ss;
ans[i-1] = res[i];
}
return ans;
}
int st = 0;
for(int i=1; i<=n; i++){
if(q[i].size() == 1){
st = i;
}
}
p[st] = 0;
dfs1(st);
vector<int> ans(n);
for(int i=1; i<=n; i++){
//cout<<sz[i]<<'\n';
if(sz[i] <= A){
ans[i-1] = 1;
}
else if(sz[i] <= A + B){
ans[i-1] = 2;
}
else{
ans[i-1]=3;
}
}
return ans;
return ans;
}
