#include <bits/stdc++.h>
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
const int N = 1e5 + 5;
int n, m;
pair<int, int> a[3];
vector<int> g[N];
int ans[N];
int sz[N];
int low[N], in[N];
int tim;
bool ok = false;
int lim;
void go(int u, int c) {
if(ans[u] != 0 || lim == 0) return;
--lim;
ans[u] = c;
for(int v : g[u]) {
if(in[v] >= in[u]) go(v, c);
}
}
int dfs(int u) {
if(sz[u] != 0 || ok) return 0;
sz[u] = 1;
in[u] = low[u] = ++tim;
int mx = 0;
for (int v : g[u]) {
int sus = dfs(v);
mx = max(mx, sus);
sz[u] += sus;
low[u] = min(low[u], in[v]);
}
if(sz[u] >= a[0].first && mx < a[0].first) {
int S = n - sz[u];
for(int v : g[u]) {
if(S >= a[0].first) break;
if(in[v] < in[u] || low[v] >= in[u]) continue;
S += sz[v];
in[v] = 0;
}
ok = true;
if(S >= a[0].first) {
if(S < a[1].first) swap(a[0], a[1]);
lim = a[0].first;
go(u, a[0].second);
memset(in, 0, sizeof in);
lim = a[1].first;
go(0, a[1].second);
for(int i = 0; i < n; ++i) if(ans[i] == 0) ans[i] = a[2].second;
}
}
return sz[u];
}
vector<int> find_split(int _n, int _a, int b, int c, vector<int> p, vector<int> q) {
n = _n;
m = p.size();
a[0] = {_a, 1};
a[1] = {b, 2};
a[2] = {c, 3};
sort(a, a + 3);
for(int i = 0; i < m; ++i) {
g[p[i]].emplace_back(q[i]);
g[q[i]].emplace_back(p[i]);
}
dfs(0);
vector<int> res(n);
for(int i = 0; i < n; ++i) res[i] = ans[i];
return res;
}
//int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(0), cout.tie(0);
//
// file("A") else file("task");
//
// cin >> n >> m;
// for(int i = 0; i < 3; ++i) {
// cin >> a[i].first;
// a[i].second = i + 1;
// }
// sort(a, a + 3);
// for(int i = 1; i <= m; ++i) {
// int u, v;
// cin >> u >> v;
// g[u].emplace_back(v);
// g[v].emplace_back(u);
// }
// dfs(0);
// for(int i = 0; i < n; ++i) cout << ans[i] << ' ';
// return 0;
//}
