#include "split.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> find_split(int n, int A, int B, int C, vector<int> P, vector<int> Q) {
array<pair<int, int>, 3> att;
att[0] = {A, 1}; att[1] = {B, 2}; att[2] = {C, 3};
sort(att.begin(), att.end());
A = att[0].first; B = att[1].first; C = att[2].first;
vector<int> sz(n, 1);
vector<vector<int>> adj(n);
vector<int> p(n);
vector<int> vis(n, 0);
vector<int> hgh(n);
vector<int> dpth(n, 0);
for (size_t i = 0; i < P.size(); i++) {
adj[P[i]].push_back(Q[i]);
adj[Q[i]].push_back(P[i]);
}
int base = 0;
function<void(int)> dfs = [&](int a) {
if (base > 0) return;
bool ok = 1;
vis[a] = 1; hgh[a] = dpth[a];
for (int x : adj[a]) {
if (vis[x]) {
if (x != p[a]) hgh[a] = min(hgh[a], dpth[x]);
continue;
}
p[x] = a;
dpth[x] = dpth[a]+1;
dfs(x);
sz[a] += sz[x];
if (sz[x] >= A) {
ok = 0;
}
}
if (sz[a] < A) ok = 0;
if (ok) {
int aus = n-sz[a];
base = a;
for (int x : adj[a]) {
if (x == 0 || p[x] != a) continue;
if (aus >= A && n-aus >= A) break;
if (hgh[x] < dpth[a]) aus += sz[x];
p[x] = p[a];
}
if (aus < A || n-aus < A) base = -1;
}
};
p[0] = -1;
dfs(0);
if (base <= 0) return vector<int> (n, 0);
vis = vector<int> (n, -1);
int ja = 0, jb = 0;
function<void(int)> dfsa = [&](int a) {
if (ja < A) {
vis[a] = att[0].second; ja++;
} else return;
for (int x : adj[a]) {
if (x == 0 || p[x] != a) continue;
dfsa(x);
}
};
dfsa(base);
function<void(int)> dfsb = [&](int a) {
vis[a] = 0;
if (jb < B) {
vis[a] = att[1].second; jb++;
} else return;
for (int x : adj[a]) {
if (vis[x] >= 0) continue;
dfsb(x);
}
};
dfsb(p[base]);
for (int i = 0; i < n; i++) {
if (vis[i] <= 0) vis[i] = att[2].second;
}
return vis;
}
