#include <bits/stdc++.h>
using namespace std;
#define mins(x, y) (x = min(x, y))
const int MXN = 1e5+5;
int n, a, b, c, la, lb, lc;
vector<int> g[MXN], ch[MXN], ans;
bool mark[MXN], bad[MXN];
int h[MXN], mn[MXN], sz[MXN];
bool flag;
void dfs_mark(int v) {
mark[v] = 1;
for(int u : ch[v])
dfs_mark(u);
}
void dfs(int v, int p=-1) {
mn[v] = h[v] = p==-1 ? 0 : h[p]+1;
sz[v] = 1;
for(int u : g[v])
if(h[u]==-1) {
ch[v].push_back(u);
dfs(u, v);
sz[v] += sz[u];
mins(mn[v], mn[u]);
}
else if(u!=p) mins(mn[v], h[u]);
if(!flag && sz[v]>=a) {
flag = 1;
int sum=1;
for(int u : ch[v])
if(mn[u]>=h[v])
sum += sz[u];
if(sum>=a) {
if(n-sum<a) return;
mark[v] = 1;
for(int u : ch[v])
if(mn[u]>=h[v])
dfs_mark(u);
if(sum>=b) {
for(int i=0; i<n; i++)
mark[i] ^= 1;
}
}
else {
sum = sz[v];
for(int u : ch[v])
if(mn[u]<h[v] && sum-sz[u]>=a) {
bad[u] = 1;
sum -= sz[u];
}
mark[v] = 1;
for(int u : ch[v])
if(!bad[u])
dfs_mark(u);
}
}
}
void dfs_a(int v) {
ans[v] = la;
a--;
for(int u : g[v])
if(a && mark[u] && !ans[u])
dfs_a(u);
}
void dfs_b(int v) {
ans[v] = lb;
b--;
for(int u : g[v])
if(b && !mark[u] && !ans[u])
dfs_b(u);
}
vector<int> find_split(int n, int aa, int bb, int cc, vector<int> p, vector<int> q) {
::n = n;
a=aa, b=bb, c=cc;
la=1, lb=2, lc=3;
if(a>b) swap(a, b), swap(la, lb);
if(b>c) swap(b, c), swap(lb, lc);
if(a>b) swap(a, b), swap(la, lb);
for(int i=0; i<p.size(); i++) {
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
memset(h, -1, sizeof(h));
dfs(0);
int v_a=-1, v_b=-1;
for(int i=0; i<n; i++)
(mark[i] ? v_a : v_b) = i;
ans = vector<int>(n, 0);
if(v_a==-1) return ans;
dfs_a(v_a);
dfs_b(v_b);
assert(a==0);
for(int &i : ans)
if(!i)
i = lc;
return ans;
}
