#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
struct DSU {
vi e;
DSU(int n) : e(n, -1) {}
int repr(int u) {
while(e[u] >= 0) u = e[u];
return u;
}
bool join(int u, int v) {
u = repr(u);
v = repr(v);
if(u == v) return false;
if(e[u] >= e[v]) swap(u, v);
e[u] += e[v];
e[v] = u;
return true;
}
};
struct tree {
int n;
vi sz;
vector<vi> L;
tree(int N) : n(N), L(N), sz(N, 0) {}
void add_edge(int u, int v) {
L[u].push_back(v);
L[v].push_back(u);
}
void get_cent(vector<vi> &seturi, vi &Cul, int ¢) {
///presupune ca lucram de fapt cu un arbore
function<void(int, int)> dfs_sz = [&](int u, int p) {
sz[u] = 1;
for(auto it : L[u]) {
if(it == p) continue;
dfs_sz(it, u);
sz[u] += sz[it];
}
};
function<int(int, int, int)> find_c = [&](int u, int p, int vlim) {
for(auto it : L[u]) {
if(it == p) continue;
if(sz[it] * 2 > vlim) return find_c(it, u, vlim);
}
return u;
};
function<void(int, int, int)> dfs_cul = [&](int u, int p, int cul) {
seturi[cul].push_back(u);
Cul[u] = cul;
for(auto it : L[u]) {
if(it == p) continue;
dfs_cul(it, u, cul);
}
};
dfs_sz(0, -1);
cent = find_c(0, -1, sz[0]);
Cul.assign(n, 0);
int nr_cul = 0;
for(auto it : L[cent]) {
seturi.emplace_back();
dfs_cul(it, cent, nr_cul);
++nr_cul;
}
}
vi select(vi weight, vi activ, int lim) {
vi sol;
for(int i = 0; i < n; ++i) {
if(activ[i] && weight[i] >= lim) return vi{i};
}
vi viz(n, 0);
vi S;
int sum, ok = 0;
function<void(int, int)> dfs = [&](int u, int p) {
S.push_back(u);
sum += weight[u];
if(sum >= lim) {
ok = 1;
return;
}
for(auto it : L[u]) {
if(it == p) continue;
if(activ[it])
dfs(it, u);
if(ok) return;
}
};
for(int i = 0; i < n; ++i) {
if(!viz[i] && activ[i]) {
dfs(i, -1);
if(ok) return S;
sum = 0;
S.clear();
}
}
return vi();
}
};
vi find_split(int n, int a, int b, int c, vi p, vi q) {
vector<ii> Mar = {{a, 1}, {b, 2}, {c, 3}};
sort(Mar.rbegin(), Mar.rend());
int m = int(p.size());
tree T(n);
DSU helper(n);
for(int i = 0; i < m; ++i) {
if(helper.join(p[i], q[i])) {
T.add_edge(p[i], q[i]);
}
}
int cent;
vi Cul;
vector<vi> Multimi;
T.get_cent(Multimi, Cul, cent);
int nr_cul = int(Multimi.size());
DSU UF_cul(nr_cul);
tree T_cul(nr_cul);
for(int i = 0; i < m; ++i) {
int c1 = Cul[p[i]], c2 = Cul[q[i]];
if(UF_cul.join(c1, c2)) T_cul.add_edge(c1, c2);
}
vi Weight(nr_cul);
for(int i = 0; i < nr_cul; ++i) {
Weight[i] = (int)Multimi[i].size();
}
auto Cul_C = T.select(Weight, vi(nr_cul, 1), Mar[2].first);
if(Cul_C.empty()) return vi(n, 0);
set<int> NoduriC, NoduriB;
for(auto it : Cul_C) {
copy(Multimi[it].begin(), Multimi[it].end(), inserter(NoduriC, NoduriC.begin()));
}
for(int i = 0; i < n; ++i)
if(!NoduriC.count(i)) NoduriB.insert(i);
auto restrict = [&](set<int> &S, int lim) {
vi active(n, 0), weight(n, 1);
for(auto it : S) active[it] = 1;
auto alese = T.select(weight, active, lim);
S.clear();
for(auto it : alese) S.insert(it);
};
restrict(NoduriB, Mar[1].first);
restrict(NoduriC, Mar[2].first);
vi Re(n, Mar[0].second);
for(auto it : NoduriB) Re[it] = Mar[1].second;
for(auto it : NoduriC) Re[it] = Mar[2].second;
return Re;
}
