#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];
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, int num){
if (num == 0) return;
answer[v] = k;
for (auto x : ed[v]){
if (x == pr) continue;
number(v, x, k, num-1);
}
}
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].rbegin(), subtr[i].rend());
if (subtr[i][1].first >= v[mn[0]] && subtr[i][0].first + 1 >= v[mn[1]]){
number(subtr[i][1].second, i, mn[0], v[mn[0]]);
number(subtr[i][0].second, i, mn[1], v[mn[1]] - 1);
answer[i] = mn[1];
flag = true;
break;
}
if (subtr[i][1].first + 1 >= v[mn[0]] && subtr[i][0].first >= v[mn[1]]){
number(subtr[i][1].second, i, mn[0], v[mn[0]] - 1);
number(subtr[i][0].second, i, mn[1], v[mn[1]]);
answer[i] = mn[0];
flag = true;
break;
}
}
if (!flag) return answer;
for (int i = 0; i < n; ++i) {
if (answer[i] == 0) answer[i] = mn[2];
}
return answer;
}
