#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];
int sz[N];
vector<int> ret;
void dfs1(int u, int p, int color, int& k) {
if (k <= 0) return;
k -= 1;
ret[u] = color;
for (const auto& v : ad[u]) {
if (v == p) continue;
dfs1(v, u, color, k);
}
}
bool doneColor = false;
void dfs(int u, int p = -1) {
if (doneColor) return;
sz[u] += 1;
bool isValid = true;
for (const auto& v : ad[u]) {
if (v == p) continue;
dfs(v, u);
sz[u] += sz[v];
if (sz[v] >= a) isValid = false;
}
if (sz[u] < a) isValid = false;
if (isValid && !doneColor && p != -1) {
doneColor = true;
dfs1(u, p, 2, a);
dfs1(p, u, 3, b);
}
}
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);
dfs(0);
if (all_of(ret.begin(), ret.end(), [&](const auto& x) { return x == 1; })) {
ret.assign(n, 0);
} else {
// assert(any_of(ret.begin(), ret.end(), [](const auto&x) {
// return x == 1;
// }));
// assert(any_of(ret.begin(), ret.end(), [](const auto&x) {
// return x == 2;
// }));
// assert(any_of(ret.begin(), ret.end(), [](const auto&x) {
// return x == 3;
// }));
}
return ret;
}
