#include <bits/stdc++.h>
#include "split.h"
using namespace std;
const int N = 100'000 + 10;
int n, a, b, c;
vector<int> ad[N];
vector<int> ret;
int sz[N];
void dfs0(int u, int p = -1) {
sz[u] = 1;
for (const auto& v : ad[u]) {
if (v == p) continue;
dfs0(v, u);
sz[u] += sz[v];
}
}
int k;
void dfs1(int u, int p, int color) {
if (k <= 0) return;
k -= 1;
ret[u] = color;
for (const auto& v : ad[u]) {
if (v == p) continue;
dfs1(v, u, color);
}
}
bool doneColor = false;
void dfs2(int u, int p = -1) {
if (doneColor) return;
bool isValid = true;
for (const auto& v : ad[u]) {
if (v == p) continue;
dfs2(v, u);
if (sz[v] >= a) isValid = false;
}
if (sz[u] < a || sz[0] - sz[u] < a) isValid = false;
if (isValid && !doneColor && p != -1) {
doneColor = true;
k = a;
dfs1(u, p, 2);
k = b;
dfs1(p, u, 3);
}
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> _p, vector<int> _q) {
{ // input
n = _n;
a = _a;
b = _b;
c = _c;
for (int i = 0; i < (int)_p.size(); ++i) {
int u = _p[i], v = _q[i];
ad[u].push_back(v);
ad[v].push_back(u);
}
if (a > b) swap(a, b);
if (b > c) swap(b, c);
if (a > b) swap(a, b);
}
assert((int)_p.size() == n - 1);
ret.resize(n, 1);
dfs0(0);
dfs2(0);
if (all_of(ret.begin(), ret.end(), [&](const auto& x) { return x == 1; })) {
ret.assign(n, 0);
} else {
int cntA = 0, cntB = 0, cntC = 0;
for (const auto& x : ret) {
(x == 1 ? cntC : x == 3 ? cntB : cntA) += 1;
}
if (cntA != a || cntB != b || cntC != c) {
cerr << "Wrong\n";
for (;;);
}
assert(cntA == a);
assert(cntB == b);
assert(cntC == c);
}
return ret;
}
