#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 12;
vector<int> g[N], gt[N], G[N], res, f[N];
int c[N], s[N];
bool vis[N];
void dfs(int v) {
s[v] = 1;
vis[v] = 1;
for(int to:g[v]) if(!vis[to]) {
dfs(to);
gt[v].push_back(to);
gt[to].push_back(v);
s[v] += s[to];
}
}
int n;
int find(int v, int pr = -1) {
for(int to:gt[v]) {
if(to != pr && s[to] > n / 2) {
return find(to, v);
}
}
return v;
}
vector<pair<int, int>> a;
int bf = 0, t;
void go(int v, int pr) {
s[t]++;
c[v] = t;
f[t].push_back(v);
for(int to:gt[v]) {
if(to != pr) {
go(to, v);
}
}
}
vector<int> st;
int sum = 0;
void dfs1(int v) {
st.push_back(v);
sum += s[v];
vis[v] = 1;
for(int to:G[v]) {
if(!vis[to]) {
dfs1(to);
}
}
}
bool good[N], used[N];
void col(int v) {
used[v] = 1;
if(a[0].first) {
res[v] = a[0].second;
--a[0].first;
}
for(int to:g[v]) {
if(good[c[to]] && !used[to]) {
col(to);
}
}
}
void make(int v) {
vis[v] = 1;
if(!res[v]) {
if(a[1].first) {
a[1].first--;
res[v] = a[1].second;
} else {
res[v] = a[2].second;
}
}
for(int to:g[v]) {
if(!vis[to] && !res[to]) {
make(to);
}
}
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
n = _n;
res.assign(n, 0);
for(int i = 0; i < (int)p.size(); i++) {
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
dfs(0);
a.push_back({_a, 1});
a.push_back({_b, 2});
a.push_back({_c, 3});
sort(a.begin(), a.end());
int v = find(0);
memset(s, 0, sizeof(s));
for(int to:gt[v]) {
t++;
go(to, v);
}
for(int i = 0; i < (int)q.size(); i++) {
int x = c[q[i]], y = c[p[i]];
if(!x || !y) continue;
if(x != y) {
G[x].push_back(y);
G[y].push_back(x);
}
}
memset(vis, 0, sizeof(vis));
bool fnd = 0;
for(int i = 1; i <= t; i++) {
if(!vis[i]) {
dfs1(i);
if(sum < a[0].first) {
sum = 0;
st.clear();
continue;
}
fnd = 1;
sum = 0;
for(int j = 0; j < (int)st.size() && sum < a[0].first; j++) {
sum += s[st[j]];
good[st[j]] = 1;
}
col(f[st[0]][0]);
break;
}
}
if(!fnd) {
return res;
}
memset(vis, 0, sizeof(vis));
make(v);
for(int i = 0; i < n; i++) {
if(!res[i]) {
res[i] = a[2].second;
}
}
return res;
}
