#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<vector<int>> adj(n);
for (int i = 0; i < (int)p.size(); i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
vector<array<int, 2>> color = {{a, 1}, {b, 2}, {c, 3}};
sort(color.begin(), color.end());
vector<vector<pair<int, int>>> sub(n);
auto dfs1 = [&](auto dfs, int u = 0, int p = -1) -> int {
int tot = 1;
for (int v : adj[u]) if (v != p) {
int sz = dfs(dfs, v, u);
sub[u].push_back(pair<int, int>{sz, v});
tot += sz;
}
if (tot != n) sub[u].push_back(pair<int, int>{n-tot, p});
return tot;
};
dfs1(dfs1);
vector<int> ans(n, color[2][1]);
auto dfs2 = [&](auto dfs, int &need, int col, int u, int p) -> void {
if (!need) return;
ans[u] = col;
need--;
for (int v : adj[u]) if (v != p) dfs(dfs, need, col, v, u);
};
for (int i = 0; i < n; i++) for (auto [sz1, j] : sub[i]) {
int sz2 = n-sz1;
if (color[0][0] <= sz1 && color[1][0] <= sz2) {
dfs2(dfs2, color[0][0], color[0][1], j, i);
dfs2(dfs2, color[1][0], color[1][1], i, j);
return ans;
}
if (color[1][0] <= sz1 && color[0][0] <= sz2) {
dfs2(dfs2, color[0][0], color[0][1], i, j);
dfs2(dfs2, color[1][0], color[1][1], j, i);
return ans;
}
}
return vector<int>(n);
}
