// sub1-3
#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef long long ll;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
const int MAXN = 100100;
int A = 0, B = 0, C = 0;
int va = 1, vb = 2, vc = 3;
int size[MAXN] = {0};
void dfs(vvi &adj, int v, vvi &tre) {
size[v] = 1;
for (int u: adj[v]) {
if (size[u] == 0) {
tre[v].push_back(u);
tre[u].push_back(v);
dfs(adj, u, tre);
size[v] += size[u];
}
}
}
void fillSub(vvi &tre, int v, int p, int value, vi &ans) {
if ((value == va && A == 0) || (value == vb && B == 0)) return;
ans[v] = value;
if (value == va) --A;
else --B;
for (int u : tre[v]) {
if (u == p) continue;
fillSub(tre, u, v, value, ans);
}
}
vi find_split(int n, int a, int b, int c, vi p, vi q) {
if (a > b) swap(a, b), swap(va, vb);
if (a > c) swap(a, c), swap(va, vc);
if (b > c) swap(b, c), swap(vb, vc);
A = a, B = b, C = c;
vvi adj(n);
for (int i = 0; i < sz(p); ++i) adj[p[i]].push_back(q[i]), adj[q[i]].push_back(p[i]);
vvi tre(n);
int root = 0;
dfs(adj, root, tre);
vi ans(n, root);
while (true) {
vpii children;
for (int u: adj[root]) children.push_back({size[u], u});
sort(all(children));
reverse(all(children));
int submax = children.front().second;
if (size[submax] < a) return ans;
else if (size[submax] > n - a) {
// move the root
size[root] = n - size[submax];
size[submax] = n;
root = submax;
} else {
ans.assign(n, vc);
// construct solution:
if (size[submax] >= b) {
swap(va, vb);
swap(A, B);
}
// subtree filled
fillSub(tre, submax, root, va, ans);
// fill rest
fillSub(tre, root, submax, vb, ans);
return ans;
}
}
}
