#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
pair<int, int> target[3];
vector<int> adj[MAXN];
vector<int> res;
int subSz[MAXN]; int n;
int dfs2(int v, int pai, int get, int c) {
if (get <= 0) return 0;
res[v] = c;
int got = 1;
for (int viz : adj[v]) {
if (viz == pai) continue;
got += dfs2(viz, v, get - got, c);
}
return got;
}
bool dfs(int v, int pai) {
// cerr << v << endl;
subSz[v] = 1;
for (int viz : adj[v]) {
if (viz == pai) continue;
if (dfs(viz, v)) return true;
subSz[v] += subSz[viz];
}
if (pai == -1) return false;
if (subSz[v] >= target[0].first and n - subSz[v] >= target[1].first) {
dfs2(v, pai, target[0].first, target[0].second);
dfs2(pai, v, target[1].first, target[1].second);
return true;
}
if (n - subSz[v] >= target[0].first and subSz[v] >= target[1].first) {
dfs2(v, pai, target[1].first, target[1].second);
dfs2(pai, v, target[0].first, target[0].second);
return true;
}
return false;
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n = N;
for (int i=0; i<n-1; i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
target[0] = make_pair(a, 1);
target[1] = make_pair(b, 2);
target[2] = make_pair(c, 3);
sort(target, target+3);
res = vector<int> (n, -1);
if (!dfs(0, -1))
res = vector<int> (n, 0);
else {
for (int i=0; i<n; i++) {
if (res[i] == -1) res[i] = target[2].second;
}
}
return res;
}
