#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
vector<int> adj[MAXN];
int a, b, c, n, m, ans[MAXN], sz[MAXN], T[4] = {0, 1, 2, 3};
bool flag = true;
void dfs_ans(int v, int p, int c) {
ans[v] = c;
for (int u : adj[v]) {
if (u == p) continue;
dfs_ans(u, v, c);
}
}
void dfs1(int v, int p) {
sz[v] = 1;
for (int u : adj[v]) {
if (u == p) continue;
dfs1(u, v);
sz[v] += sz[u];
if (!flag && sz[u] >= a && n - sz[u] >= b) {
flag = true;
dfs_ans(u, v, 1);
dfs_ans(v, u, 2);
}
if (!flag && sz[u] >= b && n - sz[u] >= a) {
flag = true;
dfs_ans(u, v, 2);
dfs_ans(v, u, 1);
}
}
}
vector<int> find_split(int n_, int a_, int b_, int c_, vector<int> p_, vector<int> q_) {
n = n_, a = a_, b = b_, c = c_;
if (b > c) swap(b, c), swap(T[2], T[3]);
if (a > c) swap(a, c), swap(T[1], T[3]);
if (a > b) swap(a, b), swap(T[1], T[2]);
m = p_.size();
for (int i = 0; i < m; i++) {
int u = p_[i], v = q_[i];
u++, v++;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs1(1, 0);
if (*max_element(ans + 1, ans + n + 1) > 0) {
for (int i = 1; i <= n; i++)
if (ans[i] == 0)
ans[i] = 3;
}
vector<int> res;
for (int i = 1; i <= n; i++)
res.push_back(T[ans[i]]);
return res;
}
