// Author: Kajetan Ramsza
#include "split.h"
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
#ifdef DEBUG
auto& operator<<(auto& os, const pair<auto, auto> &p);
auto& operator<<(auto &os, const auto &v)
{ os<<"{"; for(auto it=begin(v);it!=end(v);++it) {
if(it != begin(v)) { os<<", "; } os<<(*it);
} return os<<"}"; }
auto& operator<<(auto &os, const pair<auto, auto> &p)
{ return os<<"("<<p.first<<", "<<p.second<<")"; }
void dbg_out(auto... x) { ((cerr<<' '<<x), ...) << endl; }
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x)
#else
#define dbg(...)
#endif
int n;
vector<vi> g;
vector<bool> visited;
vi siz, parent;
void dfs(int v) {
visited[v] = true;
siz[v] = 1;
for(auto e : g[v]) {
if(visited[e]) continue;
dfs(e);
parent[e] = v;
siz[v] += siz[e];
}
}
void init() {
parent.assign(n, -1);
visited.assign(n, 0);
siz.assign(n, 0);
dfs(0);
fill(all(visited), false);
dbg(parent);
dbg(siz);
}
int select_k(int v, int k, vi &sel, bool par, int num) {
dbg(v, k, sel, par, num);
visited[v] = true;
k--;
sel[v] = num;
for(auto e : g[v]) {
if(k == 0) break;
if(visited[e]) continue;
if(par && parent[e] != v) continue;
k = select_k(e, k, sel, par, num);
}
return k;
}
pair<bool, vi> solve(vi vals, vi order) {
dbg(vals);
dbg(order);
rep(v,0,n) {
if(parent[v] == -1) continue;
dbg(v, siz[v], n-siz[v]);
if(siz[v] >= vals[order[0]] && n-siz[v] >= vals[order[1]]) {
vi sel(n, order[2]+1);
select_k(v, vals[order[0]], sel, true, order[0]+1);
select_k(parent[v], vals[order[1]], sel, false, order[1]+1);
return {true, sel};
}
if(siz[v] >= vals[order[1]] && n-siz[v] >= vals[order[0]]) {
vi sel(n, order[2]+1);
select_k(v, vals[order[1]], sel, true, order[1]+1);
select_k(parent[v], vals[order[0]], sel, false, order[0]+1);
return {true, sel};
}
}
return {false, {}};
}
vi find_split(int N, int a, int b, int c, vi p, vi q) {
n = N;
g.resize(n);
rep(i,0,sz(p)) {
g[p[i]].emplace_back(q[i]);
g[q[i]].emplace_back(p[i]);
}
init();
vi vals = {a, b, c};
vi order = {0, 1, 2};
sort(all(order), [&](int x, int y) {
return vals[x] < vals[y];
});
auto [poss, vec] = solve(vals, order);
if(poss) return vec;
return vi(n, 0);
}
