#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
vector<int> adj[MAXN], res;
int sub[MAXN], val[4];
void dfs(int s, int p, int x){
if(val[x] == 0)return;
val[x]--; res[s] = x;
for(int viz : adj[s])
if(viz != p)dfs(viz,s,x);
}
int dfsIni(int s, int p){
sub[s] = 1;
for(int viz : adj[s])
if(viz != p){
int x = dfsIni(viz,s);
if(x)return 1;
sub[s] += sub[viz];
}
for(int i = 1; i <= 3; i++)
if(val[i] == sub[i]){
dfs(s,p,i); val[i] = 0;
int nxt = i+1; if(nxt == 4)nxt = 1;
dfs(p,s,nxt);
return 1;
}
return 0;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
res.resize(n);
for(int i = 0; i < p.size(); i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
for(int i = 0; i < n; i++)res[i] = 0;
val[1] = a; val[2] = b; val[3] = c;
int x = dfsIni(0,-1);
if(x != 0){
for(int i = 0; i < n; i++)
if(res[i] == 0){
for(int j = 1; j <= 3; j++)
if(val[j] > 0){res[i] = j; val[j]--;}
}
}
return res;
}
