#include "split.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
using int64 = long long;
using ld = long double;
constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
vector<int> reject(const int n) {
vector<int> v(n);
return v;
}
vector<int> find_split(int n, int A, int B, int C, vector<int> P, vector<int> Q) {
vector<pair<int, int>> v = {{A, 1}, {B, 2}, {C, 3}};
sort(v.begin(), v.end());
A = v[0].first, B = v[1].first, C = v[2].first;
const int m = P.size();
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
const int x = P[i], y = Q[i];
g[x].push_back(y);
g[y].push_back(x);
}
vector<int> ss(n, 1);
int U = -1, V = -1;
function<int(int, int)> dfs = [&](const int x, const int p) {
for (const int y : g[x]) {
if (y == p) continue;
ss[x] += dfs(y, x);
}
if (ss[x] >= A and n - ss[x] >= B) {
U = x;
V = p;
} else if (ss[x] >= B and n - ss[x] >= A) {
U = p;
V = x;
}
return ss[x];
};
dfs(0, -1);
if (U == -1) return reject(n);
vector<int> assign(n, 3);
function<void(int, int, int, int&)> dfs2 = [&](const int x, const int p, const int i, int &sz) {
if (sz == 0) return;
sz--;
assign[x] = i;
for (const int y : g[x]) {
if (y == p) continue;
dfs2(y, x, i, sz);
}
};
dfs2(U, V, v[0].second, A);
dfs2(V, U, v[1].second, B);
return assign;
}
