#include "split.h"
#include <bits/stdc++.h>
#define pb push_back
#define oo 1000000000
#define pii pair<int, int>
using namespace std;
const int nmax = 1e5 + 5;
vector<int> ed[nmax];
vector<pii> subtr[nmax];
int cnt = 0;
vector<int> answer;
int dfs(int v, int pr, int n){
int k = 0;
for (auto to : ed[v]){
if (to == pr) continue;
subtr[v].pb({dfs(to, v, n), to});
k += subtr[v].back().first;
}
if (n - k - 1 > 0) subtr[v].pb({n - k - 1, pr});
return k + 1;
}
void number(int v, int pr, int k){
if (cnt == 0) return;
answer[v] = k;
cnt--;
for (auto x : ed[v]){
if (x == pr) continue;
number(x, v, k);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
answer.resize(n);
int m = p.size();
for (int i = 0; i < m; ++i) {
ed[p[i]].pb(q[i]);
ed[q[i]].pb(p[i]);
}
dfs(0, -1, n);
int v[4] = {oo, a, b, c};
int mn[3];
int mni = 0;
for (int i = 1; i <= 3; ++i) {
if (v[i] < v[mni]) mni = i;
}
mn[0] = mni;
int smni = 0;
for (int i = 1; i <= 3; ++i) {
if (mni == i) continue;
if (v[i] < v[smni]) smni = i;
}
mn[1] = smni;
int k = 0;
for (int i = 1; i <= 3; ++i) {
if (i != smni && i != mni) k = i;
}
mn[2] = k;
bool flag = false;
for (int i = 0; i < n; ++i) {
if (subtr[i].size() == 1) continue;
sort(subtr[i].begin(), subtr[i].end());
auto it = lower_bound(subtr[i].begin(), subtr[i].end(), make_pair(v[mn[0]], 0));
if (it == subtr[i].end()) continue;
if (n - it->first >= v[mn[1]]){
cnt = v[mn[0]];
number(it->second, i, mn[0]);
answer[i] = mn[1];
cnt = v[mn[1]] - 1;
for (auto x : subtr[i]){
if (x == *it) continue;
number(x.second, i, mn[1]);
}
flag = true;
break;
}
}
if (!flag) return answer;
for (int i = 0; i < n; ++i) {
if (answer[i] == 0) answer[i] = mn[2];
}
return answer;
}
