#include <bits/stdc++.h>
#include "split.h"
using namespace std;
const int MAX_N = 1e5 + 5;
int N, M, A, B, C;
int sz[MAX_N];
vector <int> graph[MAX_N];
vector <int> res;
bool ok;
void dfs(int u, int p, int a, int &A) {
A--;
res[u] = a;
for(auto v : graph[u]) {
if(v != p and res[v] == 0 and A > 0) {
dfs(v, u, a, A);
}
}
}
int dfs2(int u, int p) {
if(ok == true) {
return 0;
}
sz[u] = 1;
for(auto v : graph[u]) {
if(v != p) {
sz[u] += dfs2(v, u);
}
}
if(sz[u] >= A) {
if(N - sz[u] >= B) {
res.assign(N, 3);
dfs(u, p, 1, A);
dfs(p, u, 2, B);
ok = true;
return 0;
}
if(N - sz[u] >= C) {
res.assign(N, 2);
dfs(u, p, 1, A);
dfs(p, u, 3, C);
ok = true;
return 0;
}
}
if(sz[u] >= B) {
if(N - sz[u] >= A) {
res.assign(N, 3);
dfs(u, p, 2, B);
dfs(p, u, 1, A);
ok = true;
return 0;
}
if(N - sz[u] >= C) {
res.assign(N, 1);
dfs(u, p, 2, B);
dfs(p, u, 3, C);
ok = true;
return 0;
}
}
if(sz[u] >= C) {
if(N - sz[u] >= A) {
res.assign(N, 2);
dfs(u, p, 3, C);
dfs(p, u, 1, A);
ok = true;
return 0;
}
if(N - sz[u] >= B) {
res.assign(N, 1);
dfs(u, p, 3, C);
dfs(p, u, 2, B);
ok = true;
return 0;
}
}
return sz[u];
}
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;
res.resize(N, 0);
for(int i = 0; i < M; i++) {
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
}
if(M == N - 1) {
dfs2(0, -1);
}
else {
res.assign(N, 3);
int rt = 0;
for(int i = 0; i < N; i++) {
if(graph[i].size() == 1) {
rt = i;
break;
}
}
dfs(rt, -1, 2, B);
for(int i = 0; i < N; i++) {
if(res[i] == 0) {
dfs(i, -1, 1, A);
break;
}
}
}
return res;
}
