#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 11;
vector<int> G[N], sons[N];
bool vis[N]; int pa[N]; int sz[N];
void dfs(int v){
vis[v] = true;
for(auto i : G[v]){
if(!vis[i]){
dfs(i); pa[i] = v; sons[v].push_back(i);
}
}
}
void dfs2(int v){
sz[v] = 1;
for(auto i : sons[v]){
dfs2(i); sz[v] += sz[i];
}
}
vector<int> res;
int cur_sz = 0;
void bfs(int v, int par, int fil){
if(cur_sz == 0) return;
res[v] = fil; cur_sz--;
for(auto i : sons[v]){
bfs(i, v, fil);
}
}
void bfs2(int v, int par, int fil){
if(cur_sz == 0) return;
res[v] = fil; cur_sz--;
for(auto i : G[v]){
if(i != par && !res[i]) bfs2(i, v, fil);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
for(int i = 0; i < p.size(); i++){
G[p[i]].push_back(q[i]);
G[q[i]].push_back(p[i]);
}
dfs(0);
dfs2(0);
int k = min(min(a, b), c);
int v1 = 1, v2 = 2, v3 = 3;
if(a > b) swap(a, b), swap(v1, v2);
if(b > c) swap(b, c), swap(v2, v3);
if(a > b) swap(a, b), swap(v1, v2);
if(b > c) swap(b, c), swap(v2, v3);
res.resize(n);
for(int i = 0; i < n; i++){
if(sz[i] >= k && sz[i] <= n - k){
if(sz[i] <= n / 2){
cur_sz = a; bfs(i, pa[i], v1);
cur_sz = b; bfs2(pa[i], -1, v2);
for(auto& i : res) if(i == 0) i = v3;
}else{
cur_sz = b; bfs(i, pa[i], v2);
cur_sz = a; bfs2(pa[i], -1, v1);
for(auto& i : res) if(i == 0) i = v3;
}
}
}
return res;
}
