#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
using ii = pair<int, int>;
int par[100005], sz[100005];
vector<int> tp, adj[100005];
int get_sz(int u, int e = -1) {
sz[u] = 1;
for (auto v : adj[u]) if (v != e) {
par[v] = u;
sz[u] += get_sz(v, u);
}
return sz[u];
}
void topo(int u, int e = -1) {
for (auto v : adj[u]) if (v != e) {
topo(v, u);
}
tp.pb(u);
}
namespace ufds {
int lnk[100005], sz[100005];
void init(int n) {
iota(lnk, lnk + n, 0);
fill(sz, sz + n, 1);
}
int find(int x) {
if (x == lnk[x]) return x;
return lnk[x] = find(lnk[x]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) {
return;
}
if (sz[b] > sz[a]) {
swap(a, b);
}
sz[a] += sz[b];
lnk[b] = a;
}
};
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m = (int)p.size();
ufds::init(n);
for (int i = 0; i < m; i++) {
if (ufds::find(p[i]) != ufds::find(q[i])) {
adj[p[i]].pb(q[i]);
adj[q[i]].pb(p[i]);
ufds::unite(p[i], q[i]);
}
}
ii arr[3];
arr[0] = mp(a, 1);
arr[1] = mp(b, 2);
arr[2] = mp(c, 3);
sort(arr, arr + 3);
get_sz(0);
vector<int> out(n, 0);
for (int i = 0; i < n; i++) {
if (sz[i] >= arr[0].first && n - sz[i] >= arr[1].first) {
tp.clear();
topo(i, par[i]);
for (int j = 0; j < (int)tp.size(); j++) {
if (j < (int)tp.size() - arr[0].first) {
out[tp[j]] = arr[2].second;
} else {
out[tp[j]] = arr[0].second;
}
}
tp.clear();
topo(par[i], i);
for (int j = 0; j < (int)tp.size(); j++) {
if (j < (int)tp.size() - arr[1].first) {
out[tp[j]] = arr[2].second;
} else {
out[tp[j]] = arr[1].second;
}
}
break;
}
if (n - sz[i] >= arr[0].first && sz[i] >= arr[1].first) {
swap(arr[0], arr[1]);
tp.clear();
topo(i, par[i]);
for (int j = 0; j < (int)tp.size(); j++) {
if (j < (int)tp.size() - arr[0].first) {
out[tp[j]] = arr[2].second;
} else {
out[tp[j]] = arr[0].second;
}
}
tp.clear();
topo(par[i], i);
for (int j = 0; j < (int)tp.size(); j++) {
if (j < (int)tp.size() - arr[1].first) {
out[tp[j]] = arr[2].second;
} else {
out[tp[j]] = arr[1].second;
}
}
break;
}
}
return out;
}
