#include <bits/stdc++.h>
#include "split.h"
#define ll long long
#define ar array
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<vector<int>> adj(n);
int m = sz(p);
for (int i = 0; i < m; i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
if (m == n-1) {
vector<int> sub(n), p(n, -1);
auto dfs = [&](auto&& s, int v) -> void {
sub[v] = 1;
for (int u : adj[v]) if (u != p[v]) {
p[u] = v;
s(s, u);
sub[v] += sub[u];
}
};
dfs(dfs, 0);
ar<int, 3> size{a, b, c};
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if (i != j) {
int other = 3 - i - j;
for (int k = 0; k < n; k++) if (sub[k] >= size[i] && n - sub[k] >= size[j]) {
vector<int> col(n, other+1);
auto color = [&](auto&& s, int v, int P, int& left, int who) -> void {
if (!left) return;
col[v] = who;
left--;
for (int u : adj[v]) if (u != P) s(s, u, v, left, who);
};
color(color, k, p[k], size[i], i+1);
color(color, p[k], k, size[j], j+1);
return col;
}
}
return vector<int>(n);
}
for (int t = 0; t < 20; t++) {
for (int i = 0; i < n; i++) shuffle(all(adj[i]), rng);
for (int r = 0; r < n; r++) {
vector<int> sub(n), p(n, -1);
vector<bool> vis(n);
vector<vector<int>> adj2(n);
auto dfs = [&](auto&& s, int v) -> void {
sub[v] = 1, vis[v] = 1;
for (int u : adj[v]) if (!vis[u]) {
p[u] = v;
adj2[u].push_back(v);
adj2[v].push_back(u);
s(s, u);
sub[v] += sub[u];
}
};
dfs(dfs, r);
ar<int, 3> size{a, b, c};
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if (i != j) {
int other = 3 - i - j;
for (int k = 0; k < n; k++) if (sub[k] >= size[i] && n - sub[k] >= size[j]) {
vector<int> col(n, other+1);
auto color = [&](auto&& s, int v, int P, int& left, int who) -> void {
if (!left) return;
col[v] = who;
left--;
for (int u : adj2[v]) if (u != P) s(s, u, v, left, who);
};
color(color, k, p[k], size[i], i+1);
color(color, p[k], k, size[j], j+1);
return col;
}
}
}
}
return vector<int>(n);
}
