#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>> g(n), adj(n);
for (int i = 0; i < (int)p.size(); i++) {
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
vector<int> seen(n);
auto dfs1 = [&](auto dfs, int u = 0) -> void {
if (seen[u]) return;
seen[u] = 1;
for (int v : g[u]) if (!seen[v]) {
adj[u].push_back(v);
adj[v].push_back(u);
dfs(dfs, v);
}
};
dfs1(dfs1);
vector<array<int, 2>> color = {{a, 1}, {b, 2}, {c, 3}};
sort(color.begin(), color.end());
vector<vector<pair<int, int>>> sub(n);
vector<int> mxsub(n);
auto dfs2 = [&](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});
mxsub[u] = max(mxsub[u], sz);
tot += sz;
}
if (tot != n) sub[u].push_back(pair<int, int>{n-tot, p});
return tot;
};
dfs2(dfs2);
vector<int> ans(n, color[2][1]);
auto dfs3 = [&](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);
};
auto color2 = color;
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) {
dfs3(dfs3, color[0][0], color[0][1], j, i);
dfs3(dfs3, color[1][0], color[1][1], i, j);
return ans;
}
if (color[1][0] <= sz1 && color[0][0] <= sz2) {
dfs3(dfs3, color[0][0], color[0][1], i, j);
dfs3(dfs3, color[1][0], color[1][1], j, i);
return ans;
}
}
color = color2;
int rem = 0;
for (int i = 0; i < n; i++) if (mxsub[i] < color[0][0]) { rem = i; break; }
seen = vector<int>(n);
vector<int> s;
auto dfs4 = [&](auto dfs, int u) -> void {
if (seen[u] || u == rem) return;
seen[u] = 1;
s.push_back(u);
for (int v : g[u]) dfs(dfs, v);
};
bool ok = 0;
for (int i = 0; i < n; i++) {
s.clear();
dfs4(dfs4, i);
if ((int)s.size() >= color[0][0]) {
for (int u : s) ans[u] = color[0][1];
ok = 1;
break;
}
}
if (!ok) return vector<int>(n);
auto dfs5 = [&](auto dfs, int u) -> void {
if (ans[u] != color[2][1]) return;
if (!color[1][0]) return;
color[1][0]--;
ans[u] = color[1][1];
for (int v : g[u]) dfs(dfs, v);
};
dfs5(dfs5, rem);
return ans;
}
