#include <bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
const int MAX_N = 1e5;
vector<int> adj[MAX_N];
void dfs(int u, vector<int> &vis, int &b, int color, int p = -1) {
if (!b) return;
vis[u] = color;
b--;
for (int v : adj[u]) if (v != p) {
if (vis[v] != color) dfs(v, vis, b, color, u);
}
}
int sz[MAX_N], par[MAX_N];
int getSize(int u, int p = -1) {
par[u] = p, sz[u] = 1;
for (int v : adj[u]) if (v != p) {
sz[u] += getSize(v, u);
}
return sz[u];
}
vector<int> find_split(int n, int a, int b, int c, vector<int> s, vector<int> e) {
int color[3] = {1, 2, 3};
if (a > b) {
swap(a, b);
swap(color[0], color[1]);
}
if (a > c) {
swap(a, c);
swap(color[0], color[2]);
}
if (b > c) {
swap(b, c);
swap(color[1], color[2]);
}
int m = sz(e);
for (int i = 0; i < m; i++) {
adj[s[i]].push_back(e[i]);
adj[e[i]].push_back(s[i]);
}
vector<int> ans(n, color[2]);
if (a == 1) {
dfs(0, ans, b, color[1]);
for (int i = 0; i < n; i++) {
if (ans[i] == color[2]) {
ans[i] = color[0];
break;
}
}
return ans;
}
if (m == n - 1) {
getSize(0);
int u = 0;
for (int i = 1; i < n; i++) {
if (sz[i] >= a && sz[i] < sz[u]) u = i;
}
if (n - sz[u] < a) return vector<int>(n, 0);
if (sz[u] < n - sz[u]) {
dfs(u, ans, a, color[0], par[u]);
dfs(par[u], ans, b, color[1], u);
} else {
dfs(u, ans, b, color[1], par[u]);
dfs(par[u], ans, a, color[0], u);
}
return ans;
}
int u = 0, p = -1;
while (b > 0) {
if (a > 0) {
ans[u] = color[0];
a--;
} else {
ans[u] = color[1];
b--;
}
for (int v : adj[u]) {
if (v != p) {
p = u;
u = v;
break;
}
}
}
return ans;
}
