#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 20;
vector<int> adj[maxn];
int sz[maxn];
int par[maxn];
int high[maxn];
int depth[maxn];
bool flag[maxn];
int color[maxn];
int n, m, a, b, c;
pair<int, int> mi;
int cnt;
void dfs1(int u) {
flag[u] = true;
sz[u] = 1;
high[u] = depth[u];
for (auto v: adj[u]) {
if (!flag[v]) {
par[v] = u;
depth[v] = depth[u] + 1;
dfs1(v);
sz[u] += sz[v];
high[u] = min(high[u], high[v]);
}
else {
high[u] = min(high[u], depth[v]);
}
}
if (sz[u] >= a) {
mi = min(mi, make_pair(sz[u], u));
}
}
void dfs2(int u) {
if (n - mi.first >= a) {
return;
}
if (u != mi.second && high[u] < depth[mi.second]) {
flag[u] = true;
mi.first -= sz[u];
return;
}
for (auto v: adj[u]) {
if (par[v] == u) {
dfs2(v);
}
}
}
void dfs3(int u) {
if (cnt == a || flag[u]) {
return;
}
color[u] = 1;
cnt++;
for (auto v: adj[u]) {
if (par[v] == u) {
dfs3(v);
}
}
}
vector<int> solve() {
mi = make_pair(n + 1, -1);
par[0] = -1;
dfs1(0);
for (int i = 0; i < n; i++) {
flag[i] = false;
}
dfs2(mi.second);
if (n - mi.first < a) {
return vector<int>(n, 0);
}
bool flip = n - mi.first < b;
if (flip) {
swap(a, b);
}
dfs3(mi.second);
for (int i = 0; i < n; i++) {
flag[i] = false;
}
for (int i = 0; i < n; i++) {
if (!color[i] && !flag[i]) {
flag[i] = true;
vector<int> comp;
comp.push_back(i);
int sz = 1;
int pt = 0;
while (pt < sz) {
int u = comp[pt++];
for (auto v: adj[u]) {
if (!color[v] && !flag[v]) {
flag[v] = true;
comp.push_back(v);
sz++;
}
}
}
if ((int)comp.size() >= b) {
for (int j = 0; j < b; j++) {
color[comp[j]] = 2;
}
}
}
}
vector<int> res(n);
for (int i = 0; i < n; i++) {
res[i] = color[i] ? (color[i] ^ (flip ? 3 : 0)) : 3;
}
return res;
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
n = _n;
m = p.size();
for (int i = 0; i < m; i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
vector<pair<int, int>> order = {{_a, 1}, {_b, 2}, {_c, 3}};
sort(order.begin(), order.end());
a = order[0].first;
b = order[1].first;
c = order[2].first;
vector<int> res = solve();
for (int i = 0; i < n; i++) {
if (res[i] > 0) {
res[i] = order[res[i] - 1].second;
}
}
return res;
}
