#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
struct dsu{
int n;
vector<int> sz, p;
dsu(int nn){
n = nn;
sz.resize(n, 1);
p.resize(n);
for(int i = 0; i < n; i++) p[i] = i;
}
int get(int x){
if(p[x] != x) p[x] = get(p[x]);
return p[x];
}
bool unite(int a, int b){
a = get(a), b = get(b);
if(a == b) return 0;
if(sz[b] > sz[a]) swap(a, b);
sz[a]+=sz[b];
sz[b] = 0;
p[b] = a;
return 1;
}
};
int n, m;
vector<int> s, so;
vector<vector<int>> v;
vector<int> sz;
vector<int> ans;
void pre_dfs(int nd, int ss = -1){
for(int x: v[nd]) if(x != ss) pre_dfs(x, nd), sz[nd]+=sz[x];
}
int cnt;
void create_ans(int nd, int ss, int avoid, int id){
if(cnt == 0) return;
ans[nd] = id;
cnt--;
for(int x: v[nd]) if(x != ss && x != avoid && cnt) create_ans(x, nd, avoid, id);
}
void dfs(int nd, int ss = -1){
if(ans.back()) return;
if(sz[nd] >= s[0] && n-sz[nd] >= s[1]){
fill(ans.begin(), ans.end(), so[2]+1);
cnt = s[0];
create_ans(nd, ss, -1, so[0]+1);
cnt = s[1];
create_ans(0, -1, nd, so[1]+1);
return;
}
else if(sz[nd] >= s[1] && n-sz[nd] >= s[0]){
fill(ans.begin(), ans.end(), so[2]+1);
cnt = s[1];
create_ans(nd, ss, -1, so[1]+1);
cnt = s[0];
create_ans(0, -1, nd, so[0]+1);
return;
}
for(int x: v[nd]) if(x != ss && !ans.back()) dfs(x, nd);
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> P, vector<int> Q){
n = _n;
s = {_a, _b, _c};
so = {0, 1, 2};
sort(so.begin(), so.end(), [&](int a, int b){
return s[a] < s[b];
});
sort(s.begin(), s.end());
m = P.size();
v.assign(n, {});
sz.assign(n, 1);
ans.assign(n, 0);
dsu ds(n);
for(int i = 0; i < m; i++) if(ds.unite(P[i], Q[i])) v[P[i]].pb(Q[i]), v[Q[i]].pb(P[i]);
pre_dfs(0);
if(s[0] == 1){
fill(ans.begin(), ans.end(), so[2]+1);
cnt = s[1];
create_ans(0, -1, -1, so[1]+1);
for(int i = 0; i < n; i++) if(ans[i] == so[2]+1){
ans[i] = so[0]+1;
break;
}
return ans;
}
dfs(0);
return ans;
}
