#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) {
int m = (int)p.size();
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
vector<int> sz(n, 0);
vector<int> pr(n, -1);
vector<int> low(n, -1), tin(n, -1);
int tt = 0;
function<void(int, int)> dfs = [&](int v, int pred) {
sz[v] = 1;
pr[v] = pred;
tin[v] = low[v] = tt++;
for (int to : g[v]) {
if (to == pred) {
continue;
}
if (tin[to] != -1) {
low[v] = min(low[v], tin[to]);
} else {
dfs(to, v);
sz[v] += sz[to];
low[v] = min(low[v], low[to]);
}
}
};
dfs(0, -1);
vector<pair<int, int>> ve = {{a, 1}, {b, 2}, {c, 3}};
sort(ve.begin(), ve.end());
vector<int> ans(n, 0);
auto color = [&](int from, int cnt, int col, vector<bool>& was) -> void {
queue<int> que;
que.push(from);
was[from] = true;
que.push(from);
ans[from] = col;
int paint = 1;
while (!que.empty() && paint < cnt) {
int v = que.front();
que.pop();
for (int to : g[v]) {
if (was[to]) {
continue;
}
que.push(to);
was[to] = true;
if (paint < cnt) {
paint++;
ans[to] = col;
}
if (paint == col) {
return;
}
}
}
};
int cent = -1;
for (int i = 0; i < n; i++) {
if ((n - sz[i]) > n / 2) {
continue;
}
bool ok = true;
for (int to : g[i]) {
if (pr[to] == i && sz[to] > n / 2) {
ok = false;
break;
}
}
if (ok) {
cent = i;
break;
}
}
vector<int> cand;
int sum = n - sz[cent];
for (int to : g[cent]) {
if (pr[to] != cent) {
continue;
}
if (sz[to] >= ve[0].first) {
vector<bool> was(n, false);
was[cent] = true;
color(to, ve[0].first, ve[0].second, was);
was[cent] = false;
for (int i = 0; i < n; i++) {
if (ans[i] != 0) {
was[i] = true;
}
}
color(cent, ve[1].first, ve[1].second, was);
for (int i = 0; i < n; i++) {
if (ans[i] == 0) {
ans[i] = ve.back().second;
}
}
return ans;
}
if (low[to] < tin[cent]) {
cand.push_back(to);
sum += sz[to];
}
}
if (sum >= ve[0].first) {
vector<bool> is_a(n, false);
vector<bool> sel(n, false);
int cur = n - sz[cent];
vector<int> has;
for (int v : cand) {
if (cur < ve[0].first) {
cur += sz[v];
has.push_back(v);
sel[v] = true;
}
}
vector<bool> was(n, false);
was[cent] = true;
for (int to : g[cent]) {
if (pr[to] == cent && !sel[to]) {
was[to] = true;
}
}
int start = (pr[cent] != -1 ? pr[cent] : has[0]);
color(start, ve[0].first, ve[0].second, was);
vector<bool> was2(n, false);
for (int i = 0; i < n; i++) {
if (ans[i] != 0) {
was2[i] = true;
}
}
color(cent, ve[1].first, ve[1].second, was2);
for (int i = 0; i < n; i++) {
if (ans[i] == 0) {
ans[i] = ve.back().second;
}
}
return ans;
}
return ans;
}
