#include "split.h"
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
vector<vector<int>> A;
vector<ll> sz; ll n;
bool found=0;
void build(ll u, ll p, vector<int> &vals, ll wr, ll &cnt){
vals[u]=wr; cnt--;
if (cnt==0) return;
for (auto v:A[u]){
if (v==p) continue;
build(v, u, vals, wr, cnt);
if (cnt==0) return;
}
}
void dfs(ll u, ll p, vector<array<ll, 2>> &cs, vector<int> &vals){
vector<pair<ll, ll>> szs; ll csz=1;
for (auto v:A[u]){
if (v==p) continue;
dfs(v, u, cs, vals);
if (found) return;
csz+=sz[v]; szs.push_back({sz[v], u});
}
if (u!=p) szs.push_back({n-csz, p});
sort(szs.rbegin(), szs.rend());
for (ll i=0; i<(ll)szs.size(); i++){
if (szs[i].ff>=cs[1][0] and n-szs[i].ff>=cs[0][0]){
found=1; vals.assign(n, cs[2][1]);
build(szs[i].ss, u, vals, cs[1][1], cs[1][0]);
build(u, szs[i].ss, vals, cs[0][1], cs[0][0]);
return;
}
if (szs[i].ff>=cs[0][0] and n-szs[i].ff>=cs[1][0]){
found=1; vals.assign(n, cs[2][1]);
build(szs[i].ss, u, vals, cs[0][1], cs[0][0]);
build(u, szs[i].ss, vals, cs[1][1], cs[1][0]);
return;
}
}
sz[u]=csz;
}
vector<int> find_split(int N, int ca, int cb, int cc, vector<int> p, vector<int> q) {
A.clear(); sz.clear(); found=0;
n=N; A.resize(n);
for (ll i=0; i<(ll)p.size(); i++){
A[p[i]].push_back(q[i]);
A[q[i]].push_back(p[i]);
}
vector<array<ll, 2>> a = {{ca, 1}, {cb, 2}, {cc, 3}};
sort(a.begin(), a.end()); sz.resize(n);
vector<int> res;
dfs(0, 0, a, res);
if (found) return res;
else return vector<int>(n, 0);
}
