#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
const ll MAXN = 1E5+16;
bool vis[MAXN];
vll adj[MAXN];
ll sz[MAXN];
ll par[MAXN];
vll ord1, ord2;
void dfs_1 (ll u, ll par) {
sz[u] = 1;
for (ll v : adj[u]) {
if (v == par) continue;
dfs_1(v, u);
sz[u] += sz[v];
}
}
void dfs_2 (ll u, ll par, ll blk, bool underBlk) {
underBlk |= u == blk;
(underBlk?ord1:ord2).push_back(u);
for (ll v : adj[u]) {
if (v == par) continue;
dfs_2(v, u, blk, underBlk);
}
}
vi find_split (int n, int aaa, int bbb, int ccc, vi us, vi vs) {
pair <ll, ll> pa = { aaa, 1 }, pb = { bbb, 2 }, pc = { ccc, 3 };
if (pa > pb) swap(pa, pb);
if (pb > pc) swap(pb, pc);
if (pa > pb) swap(pa, pb);
ll a = pa.first, b = pb.first, c = pc.first;
ll m = us.size();
for (ll i = 0; i < m; i++) {
adj[us[i]].push_back(vs[i]);
adj[vs[i]].push_back(us[i]);
}
dfs_1(0, 0);
ll blk1 = -16, blk2 = -16;
for (ll u = 0; u < n; u++) {
if (sz[u]>=a && n-sz[u]>=b) blk1 = u;
if (sz[u]>=b && n-sz[u]>=a) blk2 = u;
}
if (blk1 != -16) {
dfs_2(0, 0, blk1, false);
vi ans(n, pc.second);
for (ll i = 0; i < a; i++) ans[ord1[i]] = pa.second;
for (ll i = 0; i < b; i++) ans[ord2[i]] = pb.second;
return ans;
}
if (blk2 != -16) {
dfs_2(0, 0, blk2, false);
vi ans(n, pc.second);
for (ll i = 0; i < b; i++) ans[ord1[i]] = pa.second;
for (ll i = 0; i < a; i++) ans[ord2[i]] = pb.second;
return ans;
}
return vi(n, 0);
}
