#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vi re(n, 0);
vector<vi> L(n);
for(int i = 0; i < p.size(); ++i) {
L[p[i]].push_back(q[i]);
L[q[i]].push_back(p[i]);
}
if(a == 1) {
vi viz(n, 0);
int nrb = 0;
function<void(int)> dfs = [&](int u) {
viz[u] = 1;
if(nrb < b) {
re[u] = 2;
++nrb;
}
for(auto it : L[u]) {
if(!viz[it])
dfs(it);
}
};
dfs(0);
for(auto &it : re) {
if(!it && a) {
it = 1;
--a;
}
if(!it) it = 3;
}
return re;
}
if(p.size() == n) {
vector<vector<int> > G(n);
vi viz(n, 0);
function<void(int)> dfs = [&](int u) {
viz[u] = 1;
for(auto it : L[u])
if(!viz[it]) {
dfs(it);
G[u].push_back(it);
G[it].push_back(u);
}
};
dfs(0);
swap(L, G);
p.pop_back();
}
if(p.size() == n - 1) {
vector<pair<int, int> > Vcul = {{a, 1}, {b, 2}, {c,3}};
sort(Vcul.begin(), Vcul.end());
int a = Vcul[0].first;
vi sz(n, 0), dpa(n, -1), fiu(n, -1);
function<void(int, int)> dfs = [&](int u, int p) {
sz[u] = 1;
dpa[u] = -1;
for(auto it : L[u]) {
if(it != p) {
dfs(it, u);
sz[u] += sz[it];
}
}
if(sz[u] >= a) {
dpa[u] = 0;
}
for(auto it : L[u]) {
if(dpa[it] != -1) {
if(dpa[u] < dpa[it] + sz[u] - sz[it]) {
dpa[u] = dpa[it] + sz[u] - sz[it];
fiu[u] = it;
}
}
}
};
dfs(0, -1);
int nra = 0, nrb = 0;
function<void(int, int, int)> dfs2 = [&](int u, int p, int tip) {
if(tip == 0 && fiu[u] == -1) {
tip = 2; /// fake news, eu sunt dfa
}
if(tip == 0) { ///dau dpa mai jos, incerc sa fiu cul1
if(nrb < Vcul[1].first) {
++nrb;
re[u] = Vcul[1].second;
} else re[u] = Vcul[2].second;
dfs2(fiu[u], u, 0);
for(auto it : L[u])
if(it != p && it != fiu[u])
dfs2(it, u, 1);
}
if(tip == 1) {
if(nrb < Vcul[1].first) {
++nrb;
re[u] = Vcul[1].second;
} else re[u] = Vcul[2].second;
for(auto it : L[u])
if(it != p)
dfs2(it, u, 1);
}
if(tip == 2) {
if(nra < Vcul[0].first) {
++nra;
re[u] = Vcul[0].second;
} else re[u] = Vcul[2].second;
for(auto it : L[u])
if(it != p)
dfs2(it, u, 2);
}
};
dfs2(0, -1, 0);
if(nra < Vcul[0].first || nrb < Vcul[1].first)
return vi(n, 0);
return re;
}
assert(0);
return re;
}
