#include <bits/stdc++.h>
using namespace std;
const int N = 100001;
int sub[N], dsu[N], color[N];
vector<int> adj[N], span[N];
bool special[N];
int find(int u) {
if (dsu[u] < 0) {
return u;
} else {
dsu[u] = find(dsu[u]);
return dsu[u];
}
}
bool unite(int u, int v) {
u = find(u), v = find(v);
if (u != v) {
if (-dsu[u] > -dsu[v]) {
swap(u, v);
}
dsu[v] += dsu[u];
dsu[u] = v;
return true;
}
return false;
}
void dfs_span(int u) {
for (auto c : adj[u]) {
if (adj[c].empty()) {
span[u].push_back(c);
span[c].push_back(u);
dfs_span(c);
}
}
}
void dfs_sub(int u, int p = -1) {
sub[u] = 1;
for (auto c : span[u]) {
if (c != p) {
dfs_sub(c, u);
sub[u] += sub[c];
}
}
}
int dfs_find(int u, int n, int p = -1) {
for (auto c : span[u]) {
if (c != p && sub[c] > n / 2) {
return dfs_find(c, n, u);
}
}
return u;
}
void dfs_unite(int u, int p = -1) {
for (auto c : span[u]) {
if (c != p) {
unite(u, c);
dfs_unite(c, u);
}
}
}
void dfs_color(int u, int x, int &y) {
color[u] = x;
--y;
for (auto c : adj[u]) {
if (special[c] == special[u] && color[c] == 0 && y > 0) {
dfs_color(c, x, y);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
fill(adj, adj + n, vector<int>());
for (int i = 0; i < (int) p.size(); ++i) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
fill(span, span + n, vector<int>());
dfs_span(0);
dfs_sub(0);
int root = dfs_find(0, n);
fill(dsu, dsu + n, -1);
for (auto u : span[root]) {
dfs_unite(u, root);
}
int ans = -1;
for (int i = 0; i < n; ++i) {
if (i != root && -dsu[find(i)] >= min({a, b, c})) {
ans = find(i);
}
}
for (int i = 0; i < n && ans == -1; ++i) {
for (auto j : adj[i]) {
if (i != root && j != root && unite(i, j)) {
if (-dsu[find(i)] >= min({a, b, c})) {
ans = find(i);
break;
}
}
}
}
if (ans == -1) {
return vector<int>(n);
}
for (int i = 0; i < n; ++i) {
special[i] = find(i) == ans;
}
int x_min, x_mid;
if (a <= min(b, c)) {
x_min = 1;
x_mid = b <= c ? 2 : 3;
} else if (b <= min(a, c)) {
x_min = 2;
x_mid = a <= c ? 1 : 3;
} else {
x_min = 3;
x_mid = a <= b ? 1 : 2;
}
int y_min = vector<int>{a, b, c}[x_min - 1];
int y_mid = vector<int>{a, b, c}[x_mid - 1];
assert(y_min <= -dsu[ans] && y_mid <= n + dsu[ans]);
fill(color, color + n, 0);
dfs_color(-dsu[ans] <= n / 2 ? ans : root, x_min, y_min);
dfs_color(-dsu[ans] <= n / 2 ? root : ans, x_mid, y_mid);
for (int i = 0; i < n; ++i) {
if (color[i] == 0) {
color[i] = x_min ^ x_mid;
}
}
return vector<int>(color, color + n);
}
