#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, node[maxn];
int tin[maxn], tout[maxn], low[maxn], sz[maxn], res[maxn];
vector<int> adj[maxn], g[maxn], cut;
pair<int,int> req[4];
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);
g[v].pb(u);
low[u] = min(low[u], low[v]);
}
else low[u] = min(low[u], tin[v]);
}
tout[u] = tin[0];
}
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) {
vector<int>().swap(cut);
for (int v : g[u])
if (low[v] > tin[u] && rem > req[1].fi) {
rem -= sz[v];
cut.pb(v);
}
}
if (rem >= req[1].fi) {
for (auto v : cut) {
for (int i = tin[v]; i <= tout[v]; i++)
res[node[i]] = 3;
}
int cnt = 0, col = 1;
for (int i = tin[u]; i <= tout[u]; i++)
if (!res[node[i]]) {
res[node[i]] = col;
cnt++;
if (cnt == req[1].fi && col == 1)
col = 3;
}
cnt = 0, col = 2;
for (int i = 1; i < tin[u]; i++) {
res[node[i]] = col;
cnt++;
if (cnt == req[2].fi && col == 2)
col = 3;
}
for (int i = tout[u] + 1; i <= n; i++) {
res[node[i]] = col;
cnt++;
if (cnt == req[2].fi && col == 2)
col = 3;
}
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 << ' ';
// }
