#include "split.h"
#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) {
vector<array<int, 2>> numbers(3);
numbers[0] = {a, 1};
numbers[1] = {b, 2};
numbers[2] = {c, 3};
sort(numbers.begin(), numbers.end());
array<int, 3> mp = {numbers[0][1], numbers[1][1], numbers[2][1]};
a = numbers[0][0]; b = numbers[1][0]; c = numbers[2][0];
vector<vector<int>> adj(n);
int m = p.size();
for(int i = 0; i<m; i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
vector<vector<int>> t(n);
vector<vector<int>> back(n);
vector<int> h(n, 0);
vector<int> sz(n, 1);
vector<bool> vis(n, 0);
function<void(int)> build_tree = [&](int v){
vis[v] = 1;
for(int u: adj[v]){
if(vis[u]) back[v].push_back(u);
else{
t[v].push_back(u);
h[u] = h[v]+1;
build_tree(u);
sz[v] += sz[v];
}
}
return;
};
build_tree(0);
//individuo i nodi possibili
vector<int> nodes;
function<void(int)> find_nodes = [&](int v){
if(sz[v] < a) return;
bool b = 1;
for(int u: t[v]){
if(sz[u] >= a){
b = 0;
find_nodes(u);
}
}
if(b) nodes.push_back(v);
return;
};
find_nodes(0);
//provo tutti i nodi fino a quando trovo uno che funziona
vector<bool> rem(n, 0);
vector<int> sl(n, 0);
for(int nd: nodes){
int curr_sz = sz[nd];
function<void(int)> try_node = [&](int v){
if(v != nd && curr_sz - sz[v] >= a){
for(int u: back[v]){
if(h[u] < h[nd]){
rem[v] = 1;
curr_sz -= sz[v];
return;
}
}
}
for(int u: t[v]){
try_node(u);
}
return;
};
try_node(nd);
if(n-curr_sz >= b){
//ho trovato la sol :D
//dfs dalla root per scegliere a
for(int i = 0; i<n; i++) sl[i] = mp[2];
int cnt = 0;
function<bool(int)> find_a = [&](int v) -> bool{
sl[v] = mp[0];
if(++cnt == a) return 1;
for(int u: t[v]){
if(rem[u]) continue;
if(find_a(u)) return 1;
}
return 0;
};
find_a(nd);
//dfs dalla root per scegliere b
cnt = 0;
vector<bool> vis2(n, 0);
function<bool(int)> find_b = [&](int v) -> bool{
sl[v] = mp[1];
if(++cnt == b) return 1;
vis2[v] = 1;
for(int u: adj[v]){
if(sl[u] == mp[0] || vis2[u]) continue;
if(find_b(u)) return 1;
}
return 0;
};
find_b(0);
return sl;
}
}
return sl;
}
