#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 4;
const int INF = 1e9;
int n, m, cnt, node[maxn];
int tin[maxn], tout[maxn], low[maxn], sz[maxn], res[maxn];
vector<int> adj[maxn], g[maxn];
map<int,int> bad;
pair<int,int> req[5];
bool ok = false;
void dfs1(int u, int p) {
// clog << u << ' ' << p << '\n';
tin[u] = low[u] = ++tin[0];
node[tin[0]] = u;
sz[u] = 1;
for (int v : adj[u]) {
if (v == p) continue;
if (!tin[v]) {
dfs1(v, u);
sz[u] += sz[v];
g[u].pb(v);
low[u] = min(low[u], low[v]);
}
else low[u] = min(low[u], tin[v]);
}
tout[u] = tin[0];
}
void dfs3(int u, int p, int col, vector<int> adj[]) { // to mau
if (cnt == req[col].fi) return;
res[u] = col;
// if (col == 1) clog << u << ' ';
cnt++;
for (int v : adj[u])
if (!bad[v] && v != p && res[v] == 3)
dfs3(v, u, col, adj);
}
void dfs2(int u, int p) {
if (ok) return;
bool flag = true;
for (int v : g[u])
if (v != p) {
dfs2(v, u);
if (sz[v] >= req[1].fi)
flag = false;
}
if (flag && sz[u] >= req[1].fi) {
int rem = n - sz[u];
if (rem < req[1].fi) {
bad.clear();
for (int v : g[u])
if (low[v] < tin[u] && rem < req[1].fi) {
rem += sz[v];
bad[v] = 1;
}
}
// clog << u << ' ' << p;
if (rem >= req[1].fi) {
for (int i = 1; i <= n; i++)
res[node[i]] = 3;
int col1 = 1, col2 = 2;
if (rem < req[2].fi)
swap(col1, col2);
dfs3(u, p, col1, g);
bad.clear(); cnt = 0;
dfs3(p, 0, col2, adj);
ok = true;
}
}
}
vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
n = _n, m = p.size();
req[1] = {a, 1}; req[2] = {b, 2}; req[3] = {c, 3};
sort(req + 1, req + 4);
for (int i = 0; i < m; i++) {
int u = p[i], v = q[i];
u++, v++;
adj[u].pb(v);
adj[v].pb(u);
}
dfs1(1, 0);
dfs2(1, 0);
vector<int> ans(n);
for (int i = 0; i < n; i++)
ans[i] = req[res[i + 1]].se;
return ans;
}
// int main()
// {
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// //freopen(".INP", "r", stdin);
// //freopen(".OUT", "w", stdout);
// int n, m, a, b, c;
// vector<int> p, q;
// cin >> n >> m >> a >> b >> c;
// for (int i = 1; i <= m; i++) {
// int u, v; cin >> u >> v;
// p.pb(u); q.pb(v);
// }
// vector<int> ans = find_split(n, a, b, c, p, q);
// for (auto i : ans)
// cout << i << ' ';
// }
