// Ignut
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 123;
int n;
int a, b, c;
int colorA, colorB, colorC;
vector<int> g[MAXN];
int sz[MAXN];
int parent[MAXN];
int flag = -1;
int vert = -1;
int dfs0(int v, int par) {
sz[v] = 1;
parent[v] = par;
for (int to : g[v])
if (to != par)
sz[v] += dfs0(to, v);
return sz[v];
}
vector<int> res;
int lim;
void dfs(int v, int par, int col) {
res[v] = col;
lim --;
if (lim == 0) return;
for (int to : g[v]) {
if (to == par || to == vert)
continue;
dfs(to, v, col);
if (lim == 0) return;
}
}
vector<int> find_split(int N, int A, int B, int C, vector<int> P, vector<int> Q) {
vector<pair<int, int>> col = {{A, 1}, {B, 2}, {C, 3}};
sort(col.begin(), col.end());
A = col[0].first, colorA = col[0].first;
B = col[1].first, colorB = col[1].first;
C = col[2].first, colorC = col[2].first;
int M = P.size();
for (int i = 0; i < M; i ++) {
g[P[i]].push_back(Q[i]);
g[Q[i]].push_back(P[i]);
}
dfs0(0, -1);
for (int i = 0; i < N; i ++) {
if (sz[i] >= A && N - sz[i] >= B) {
vert = i; flag = 1; break;
}
if (sz[i] >= B && N - sz[i] >= A) {
vert = i; flag = 2; break;
}
}
res.assign(N, 0);
if (vert == -1)
return res;
for (int i = 0; i < N; i ++) res[i] = colorC;
if (flag == 1) {
lim = B; dfs(0, -1, colorB);
lim = A; dfs(vert, parent[vert], colorA);
}
else {
lim = A; dfs(0, -1, colorA);
lim = B; dfs(vert, parent[vert], colorB);
}
return res;
}
