#include <bits/stdc++.h>
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
using namespace std;
const int N = 1e5 + 5;
vector <pair <int, int>> type(3);
vector <int> adj[N], tree[N];
int st[N], ed[N], cnt = 0, sz[N], r;
int dfs(int u){
st[u] = ++ cnt;
sz[u] = 1;
for (auto v : adj[u]){
if (!st[v]){
tree[u].pb(v);
int k = dfs(v);
sz[u] += sz[v];
if (sz[v] >= type[0].first) return k;
}
}
ed[u] = cnt;
return u;
}
vector <int> ans;
int rc[N];
bool dfs2(int u){
for (int v : tree[u]) if (dfs2(v)) return true;
for (int v : adj[u]) if (ed[v] < st[r] || st[v] > ed[r]) return true;
return false;
}
void ck(int u){
rc[u] = 1;
for (int v : tree[u]) ck(v);
}
void ass(int u, pair <int, int> &type){
if (type.first){
ans[u] = type.second;
-- type.first;
}
for (int v : tree[u]) if (!rc[v] && type.first && !ans[v] && st[r] <= st[v] && ed[v] <= ed[r]) ass(v, type);
}
void ass1(int u, pair <int, int> &type){
if (type.first){
ans[u] = type.second;
-- type.first;
}
for (int v : adj[u]) if (!ans[v] && type.first) ass1(v, type);
}
vector <int> find_split(int n, int a, int b, int c, vector <int> u, vector <int> v){
ans.resize(n, 0);
type[0] = {a, 1}, type[1] = {b, 2}, type[2] = {c, 3};
sort(ALL(type));
for (int i = 0; i < u.size(); ++ i) adj[u[i]].pb(v[i]), adj[v[i]].pb(u[i]);
r = dfs(0);
int p1 = sz[r];
int p2 = n - sz[r];
for (int v : tree[r]){
if (dfs2(v)){
if (p1 - sz[v] >= type[0].first) {
p1 -= sz[v];
p2 += sz[v];
ck(v);
}
}
}
if (p2 < type[0].first) return ans;
if (p2 >= type[1].first){
ass(r, type[0]);
ass1(0, type[1]);
}
else {
ass(r, type[1]);
ass1(0, type[0]);
}
for (int i = 0; i < n; ++ i) if (!ans[i]) ans[i] = type[2].second;
return ans;
}
//
//int main(){
// int n, m; cin >> n >> m;
// int a, b, c; cin >> a >> b >> c;
// vector <int> u, v;
// for (int i = 0; i < m; ++ i){
// int z, k; cin >> z >> k;
// u.pb(z);
// v.pb(k);
// }
//
// for (int ans : find_split(n, a, b, c, u, v)) cout << ans << ' ';
//}
