#include "split.h"
#include <bits/stdc++.h>
using namespace std;
int N,M,A,B,C, dist[100005];
vector<int> lst[100005], ans;
pair<int,int> tmp[3];
queue<int> Q;
void dfs (int x, int p, int d) {
dist[x] = d;
for (int v: lst[x]) if (v != p) dfs(v,x,d+1);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N = n, M = p.size(), A = a, B = b, C = c;
for (int i = 0; i < M; ++i) lst[p[i]].push_back(q[i]), lst[q[i]].push_back(p[i]);
dfs(0,-1,0);
pair<int,int> S = make_pair(-1,-1);
for (int i = 0; i < N; ++i) S = max(S,make_pair(dist[i],i));
dfs(S.second,-1,0);
pair<int,int> T = make_pair(-1,-1);
for (int i = 0; i < N; ++i) T = max(T,make_pair(dist[i],i));
tmp[0] = make_pair(A,1), tmp[1] = make_pair(B,2), tmp[2] = make_pair(C,3);
sort(tmp,tmp+3);
ans.assign(N,tmp[2].second);
Q.push(S.second);
ans[S.second] = tmp[0].second;
int cnt = 1;
while (!Q.empty() && cnt < tmp[0].first) {
int u = Q.front(); Q.pop();
for (int v: lst[u]) if (ans[v] == tmp[2].second) {
ans[v] = tmp[0].second, cnt++;
Q.push(v);
if (cnt >= tmp[0].first) break;
}
}
while (!Q.empty()) Q.pop();
if (cnt < tmp[0].first || ans[T.second] == tmp[0].second) return vector<int>(N,0);
Q.push(T.second);
ans[T.second] = tmp[1].second;
cnt = 1;
while (!Q.empty() && cnt < tmp[1].first) {
int u = Q.front(); Q.pop();
for (int v: lst[u]) if (ans[v] == tmp[2].second) {
ans[v] = tmp[1].second, cnt++;
Q.push(v);
if (cnt >= tmp[1].first) break;
}
}
if (cnt < tmp[1].first) return vector<int>(N,0);
return ans;
}
