#include <bits/stdc++.h>
#include "split.h"
using namespace std;
#define forinc(a, b, c) for(int a = b, _c = c; a <= _c; ++a)
#define fordec(a, b, c) for(int a = b, _c = c; a >= _c; --a)
#define rep(i, a) forinc(i, 1, a)
#define repv(i, a) forinc(i, 0, a - 1)
#define forv(a, b) for(auto &a : b)
#define ii pair<int, int>
#define fi first
#define se second
#define reset(f, x) memset(f, x, sizeof(f))
#define all(a) begin(a), end(a)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define bit(x, i) (x >> (i - 1) & 1ll)
#define on(x, i) (x | (1ll << (i - 1)))
#define off(x, i) (x & ~(1ll << (i - 1)))
const int N = 1e5 + 5;
int n, m;
int a, b, c, dd[N], req;
vector <int> ad[N];
ii ed[N];
struct dsu {
vector <int> id;
dsu(int n) {
id.resize(n, -1);
}
void init(int n) {
id.resize(n, -1);
}
int root(int x) {return id[x] < 0 ? x : id[x] = root(id[x]);}
bool com(int u, int v) {
u = root(u), v = root(v);
if(u == v) return false;
if(id[u] < id[v]) swap(u, v);
id[u] += id[v];
id[v] = u;
return true;
}
bool same(int u, int v) {
return root(u) == root(v);
}
int sz(int x) {
return -id[root(x)];
}
};
int sz[N], pd[N], cnt = 0;
int find_cen(int siz) {
function<void(int, int)> dfs = [&](int u, int par) {
sz[u] = 1;
forv(v, ad[u]) if(v != par) {
pd[v] = u;
dfs(v, u);
sz[u] += sz[v];
}
};
dfs(0, -1);
int u = 0;
pair<int, int> mx = {-1, -1};
while(1) {
mx = {-1, -1};
forv(v, ad[u]) if(v != pd[u]) mx = max(mx, make_pair(sz[v], v));
if(mx.fi <= siz) return u;
u = mx.se;
}
assert(0);
}
void col(int u, int par, int &cnt, int cl) {
if(!cnt) return;
if(dd[u]) return;
if(u == par) return;
dd[u] = cl;
cnt--;
forv(v, ad[u]) col(v, par, cnt, cl);
}
vector <int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
n = _n, a = _a, b = _b, c = _c;
int ca, cb, cc;
vector <ii> _;
_.eb(a, 1); _.eb(b, 2); _.eb(c, 3);
sort(all(_));
tie(a, ca) = _[0];
tie(b, cb) = _[1];
tie(c, cc) = _[2];
m = p.size();
repv(i, m) {
int u = p[i], v = q[i];
//ad[u].pb(v); ad[v].pb(u);
ed[i + 1] = {u, v};
}
dsu f(n);
rep(i, m) {
int u = ed[i].fi, v = ed[i].se;
if(f.com(u, v)) {
ad[u].pb(v); ad[v].pb(u);
}
}
int r = find_cen(n - b);
f.init(n);
forinc(i, 0, n - 1) {
forv(v, ad[i]) {
if(i != r && v != r) f.com(i, v);
}
}
forinc(i, 0, m - 1) {
int u = p[i], v = q[i];
if(f.sz(u) >= a || f.sz(v) >= a) continue;
if(u != r && v != r) {
if(f.com(u, v)) {
ad[u].pb(v); ad[v].pb(u);
}
}
}
forv(v, ad[r]) if(f.sz(v) >= a) {
col(v, r, a, ca);
col(r, -1, b, cb);
forinc(i, 0, n - 1) if(!dd[i]) dd[i] = cc;
break;
}
vector <int> result;
forinc(i, 0, n - 1) result.pb(dd[i]);
return result;
}
/*
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#define task "split"
if(fopen("inp.txt", "r")) {
freopen("inp.txt", "r", stdin);
}
cin >> n >> m >> a >> b >> c;
vector <int> p(m), q(m);
repv(i, m) {
cin >> p[i] >> q[i];
}
vector <int> ans = find_split(n, a, b, c, p, q);
forv(v, ans) cout << v << ' ';
}
*/
