#include "split.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const int N = 1e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
vector <int> adj[N];
vector <int> g[N];
int ans[N];
int sz[N];
int n,m,a,b,c,par,ok = -1;
int ca = 1, cb = 2, cc = 3;
bool vis[N];
void dfs(int u) {
sz[u] = 1;
vis[u] = true;
for (int v : adj[u]) if (!vis[v]) {
g[v].push_back(u);
g[u].push_back(v);
dfs(v);
sz[u] += sz[v];
if (sz[v] >= a && (n - sz[v]) >= b) {
ok = v;
par = u;
}
if (sz[v] >= b && (n - sz[v]) >= a) {
ok = u;
par = v;
}
}
}
void paint(int u, int &a, int ca, int p) {
a--;
ans[u] = ca;
for (int v : g[u]) if (v != p) {
if (a == 0)
break;
paint(v, a, ca, u);
}
}
vector<int> find_split(int _n, int _a, int _b, int _c,
vector<int> p, vector<int> q) {
m = p.size();
n = _n;
a = _a;
b = _b;
c = _c;
if (a > b) {
swap(a, b);
swap(ca, cb);
}
if (a > c) {
swap(a, c);
swap(ca, cc);
}
if (b > c) {
swap(b, c);
swap(cb, cc);
}
for (int i = 0; i < m; i++) {
auto [u, v] = tuple <int, int> {p[i], q[i]};
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(0);
if (ok != -1) {
paint(ok, a, ca, par);
paint(par, b, cb, ok);
vector <int> res;
for (int i = 0; i < n; i++) {
if (ans[i] == 0)
ans[i] = cc;
res.push_back(ans[i]);
}
return res;
}
return vector <int> (n, 0);
}
//#include "grader.cpp"
