#include <bits/stdc++.h>
#include "split.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#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 = 2e5 + 5;
vector <int> ad[N];
int id[N];
int root(int x) {return id[x] < 0 ? x : id[x] = root(id[x]);}
bool mer(int u, int v){
if((u = root(u)) == (v = root(v))) return false;
if(id[u] < id[v]) swap(u, v);
id[u] += id[v];
id[v] = u;
return 1;
}
int to(int x) {return -id[root(x)];}
int sz[N], pd[N];
int ftr(int s) {
function<void(int)> dfs = [&](int u) {
sz[u] = 1;
forv(v, ad[u]) if(v != pd[u]) {
pd[v] = u;
dfs(v);
sz[u] += sz[v];
}
};
dfs(0);
int now=0;
while(1) {
ii mx = {-1, -1};
forv(v, ad[now]) if(v != pd[now]) mx = max(mx, make_pair(sz[v], v));
if(mx.first <= s) return now;
now = mx.se;
}
assert(0);
}
vector <int> find_split(int n, int a, int b, int c, vector <int> p, vector <int> q) {
int m = p.size();
int ca = 1, cb = 2, cc = 3;
vector <ii> pp;
vector <int> dd(n, 0);
pp.eb(a, ca); pp.eb(b, cb); pp.eb(c, cc);
sort(all(pp)); tie(a, ca) = pp[0]; tie(b, cb) = pp[1], tie(c, cc) = pp[2];
reset(id, -1);
repv(i, m) {
int u = p[i], v = q[i];
if(mer(u, v)) ad[u].pb(v), ad[v].pb(u);
}
reset(id, -1);
int rt = ftr(n - b);
repv(i, n) {
forv(v, ad[i]) {
if(i != rt && v != rt) mer(i, v);
}
}
repv(i, m) {
int u = p[i], v = q[i];
if(to(u) >= a || to(v) >= a) continue;
if(u == rt || v == rt) continue;
if(mer(u, v)) {
ad[u].pb(v); ad[v].pb(u);
}
}
function<void(int, int &, int, int)> dfs=[&](int u, int &cnt, int cl, int bl) {
if(u == bl || !cnt || dd[u]) return 0;
dd[u] = cl;
cnt -= 1;
forv(v, ad[u]) if(!dd[v]) {
dfs(v, cnt, cl, bl);
}
};
forv(v, ad[rt]) if(to(v) >= a) {
dfs(v, a, ca, rt);
dfs(rt, b, cb, -1);
repv(i, n) if(!dd[i]) dd[i] = cc;
break;
}
return dd;
}
/*
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
if(fopen("inp.txt", "r")) freopen("inp.txt", "r", stdin);
int n, m, a, b, c;
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 << ' ';
}
*/
