#include <bits/stdc++.h>
#include "split.h"
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const int N = 1e5 + 7;
int n, tim, f = -1;
int bio[N], st[N], ba[N], siz[N];
vector <int> no;
vector <int> adj[N], gadj[N];
vector <pii> fo, u;
void dfs(int x, int p = -1) {
bio[x] = 1;
st[x] = tim++;
ba[x] = st[x];
siz[x] = 1;
int mx = 0, sum = 0;
for (auto y : adj[x]) {
if (y == p) continue;
if (bio[y]) {
if (st[y] < st[x]) ba[x] = min(ba[x], st[y]);
continue;
}
dfs(y, x);
ba[x] = min(ba[x], ba[y]);
siz[x] += siz[y];
mx = max(mx, siz[y]);
gadj[x].pb(y);
gadj[y].pb(x);
}
mx = max(mx, n-siz[x]);
if (mx <= n/2 && f == -1) {
f = x;
for (auto y : adj[x]) if (st[y] > st[x] && ba[y] >= st[x]) fo.pb({siz[y], y});
if (p != -1) {
u.pb({n-siz[x], p});
for (auto y : adj[x]) if (st[y] > st[x] && ba[y] < st[x]) u.pb({siz[y], y});
}
}
}
void ldfs(int x) {
no.pb(x);
bio[x] = 1;
for (auto y : gadj[x]) if (!bio[y]) ldfs(y);
}
vector <int> find_split(int nn, int a, int b, int c, vector <int> p, vector <int> q) {
n = nn;
int m = p.size();
int ca = 1, cb = 2, cc = 3;
if (a > b) {swap(a, b); swap(ca, cb);};
if (a > c) {swap(a, c); swap(ca, cc);};
if (b > c) {swap(c, b); swap(cc, cb);};
for (int i = 0; i < m; i++) {
adj[p[i]].pb(q[i]);
adj[q[i]].pb(p[i]);
}
dfs(0);
memset(bio, 0, sizeof bio);
int x = f, sum = 0;
sort(all(fo)); sort(all(u)); reverse(all(u));
for (auto it : u) sum += it.F;
vector <int> res(n, 0);
if ((fo.empty() || fo.back().F < a) && sum < a) return res;
bio[x] = 1;
for (int i = 0; i < n; i++) res[i] = cc;
if (sum < a) ldfs(fo.back().S);
else {
sum = 0;
for (int i = 0; i < u.size(); i++) {
sum += u[i].F;
if (sum < a) ldfs(u[i].S);
else {
vector <int> tmp; tmp = no; no.clear();
ldfs(u[i].S);
for (auto y : no) bio[y] = 0;
int fx = u[i].S;
for (auto y : no) {
for (auto z : adj[y]) {
if (bio[z] && z != x) fx = y;
}
if (fx != -1) break;
}
no.clear();
no = tmp;
ldfs(fx);
break;
}
}
}
for (int i = 0; i < a; i++) res[no[i]] = ca;
no.clear();
ldfs(x);
for (int i = 0; i < b; i++) res[no[i]] = cb;
return res;
}
