#include <bits/stdc++.h>
#include "split.h"
#pragma GCC optimize("O3")
using namespace std;
const int N = 1e5;
int n, A, B, C, ia, ib, ic, d;
int st[N];
vector<int> g[N], sol;
void flood1(int u, int &c, int f){
if(sol[u] || !c) return;
else sol[u] = f, c--;
for(int v : g[u]) flood1(v, c, f);
}
void st1(){
flood1(0, A, ia);
for(int i = 0; i < n; i++){
if(!sol[i]){
flood1(i, B, ib);
break;
}
}
for(int i = 0; i < n; i++) if(!sol[i]) sol[i] = ic;
}
void st2(){
flood1(0, B, ib);
for(int i = 0; i < n; i++){
if(sol[i]) continue;
if(A) sol[i] = ia, A--;
else sol[i] = ib;
}
}
void flood2(int u, int p, int &c, int f){
if(!c) return;
sol[u] = f, c--;
for(int v : g[u]) if(v != p) flood2(v, u, c, f);
}
void dfs(int u, int p){
st[u] = 1;
for(int v : g[u]){
if(v == p) continue;
dfs(v, u);
if(d) return;
st[u] += st[v];
}
if(n-st[u] >= A && st[u] >= B){
flood2(u, p, B, ib);
flood2(p, u, A, ia);
for(int i = 0; i < n; i++) if(!sol[i]) sol[i] = ic;
d = 1;
}
else if(st[u] >= A && n-st[u] >= B){
flood2(u, p, A, ia);
flood2(p, u, B, ib);
for(int i = 0; i < n; i++) if(!sol[i]) sol[i] = ic;
d = 1;
}
}
void st3(){
dfs(0, 0);
}
void tmp(int tn){
n = tn;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
int m = p.size();
for(int i = 0, u, v; i < m; i++){
u = p[i], v = q[i];
g[u].push_back(v);
g[v].push_back(u);
}
A = a, B = b, C = c, ia = 1, ib = 2, ic = 3;
if(C < B) swap(B, C), swap(ib, ic);
if(B < A) swap(A, B), swap(ia, ib);
if(C < B) swap(B, C), swap(ib, ic);
sol.resize(n);
tmp(n);
if(m == n-1) st3();
else if(A == 1) st2();
else st1();
return sol;
}
