#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <queue>
#include "split.h"
using namespace std;
#define all(a) (a).begin(), (a).end()
#define ll long long
#define ld long double
#define ui uint64_t
#define cont(set, element) ((set).find(element) != (set).end())
#define chmin(x, y) (x = min(x, y))
#define chmax(x, y) (x = max(x, y))
/********* DEBUG *********/
template <typename T>
void outvec(const vector<T>& Z){
for (const T& x : Z)
cout << x << ' ';
cout << "\n";
}
void printVariable(const any& var) {
if (!var.has_value()) {
cout << "null";
return;
}
if (var.type() == typeid(int)) {
cout << any_cast<int>(var);
} else if (var.type() == typeid(double)) {
cout << any_cast<double>(var);
} else if (var.type() == typeid(float)) {
cout << any_cast<float>(var);
} else if (var.type() == typeid(char)) {
cout << any_cast<char>(var);
} else if (var.type() == typeid(bool)) {
cout << (any_cast<bool>(var) ? "true" : "false");
} else if (var.type() == typeid(string)) {
cout << any_cast<string>(var);
} else if (var.type() == typeid(const char*)) {
cout << any_cast<const char*>(var);
} else if (var.type() == typeid(long long)) {
cout << any_cast<long long>(var);
} else {
cout << "[unknown type]";
}
}
template<typename... Args>
void outval(Args... args) {
vector<any> variables = {args...};
for (size_t i = 0; i < variables.size(); ++i) {
printVariable(variables[i]);
if (i != variables.size() - 1) {
cout << " ";
}
}
cout << "\n";
}
#define sp << " " <<
#define fi first
#define se second
/********* DEBUG *********/
const ll MOD = 1e9+7;
const ll MOD2 = 998244353;
const ll inf = 1e18;
const ll mxN = 100005;
int timer;
vector<int> low(mxN), seen(mxN), sz(mxN);
vector<vector<int>> adj(mxN);
void dfs(int u, int p = -1){
low[u] = seen[u] = ++timer;
sz[u] = 1;
for (auto &v : adj[u]){
if (!seen[v]){
dfs(v, u);
chmin(low[u], low[v]);
sz[u] += sz[v];
}
else if (v != p){
chmin(low[u], seen[v]);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
adj.assign(n, vector<int>());
seen.assign(n, 0);
timer = 0;
for (int i = 0; i < p.size(); i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
vector<pair<ll,ll>> labels = {{a, 1}, {b, 2}, {c, 3}};
sort(all(labels));
dfs(0);
for (int i = 1; i < n; i++){
// check if we're smallest possible centroid with child size >= a
bool ok = sz[i] >= labels[0].first;
for (auto &v : adj[i])
if (seen[v] > seen[i]){
ok &= (sz[v] < labels[0].first);
}
if (!ok)
continue;
// try to make smallest a size component
ll cnt = sz[i];
vector<ll> out;
for (auto &v : adj[i]){
// must not be a bridge
if (low[v] <= seen[i] && seen[i] < seen[v] && cnt - sz[v] >= labels[0].first){
out.push_back(v);
cnt -= sz[v];
}
}
// not possible
if (n - cnt < labels[0].first)
continue;
// possible, now color
if (cnt > n-cnt)
swap(labels[0], labels[1]);
vector<bool> vis(n);
for (auto &x : out)
vis[x] = true;
vector<int> ans(n, labels[2].second);
queue<int> q;
q.push(i);
vis[i] = true;
while (q.size() && labels[0].first--){
ll nd = q.front(); q.pop();
ans[nd] = labels[0].second;
for (auto &v : adj[nd]){
if (!vis[v] && seen[v] > seen[nd]){
vis[v] = true;
q.push(v);
}
}
}
while (q.size())
q.pop();
for (int j = 0; j < n; j++)
vis[j] = false;
q.push(0);
vis[0] = true;
while (q.size() && labels[1].first--){
ll nd = q.front(); q.pop();
ans[nd] = labels[1].second;
for (auto &v : adj[nd]){
if (!vis[v] && ans[v] != labels[0].second){
vis[v] = true;
q.push(v);
}
}
}
return ans;
}
return vector<int>(n);
}
