#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
vector<int> adj[MAXN], res;
int qtdb[MAXN], qtdc[MAXN], sub[MAXN], A,B,C, marc[3];
void dfsIni(int s, int p){
sub[s] = 1; qtdb[s] = 0; qtdc[s] = 0;
for(int viz : adj[s])
if(viz != p){
dfsIni(viz,s);
sub[s] += sub[viz];
qtdb[s] += qtdb[viz];
qtdc[s] += qtdc[viz];
}
if(sub[s] == B)qtdb[s]++;
if(sub[s] == C)qtdc[s]++;
}
void marcar(int s, int p, int x){
res[s] = x;
for(int viz : adj[s])
if(viz != p && res[viz] == 0)marcar(viz,s,x);
}
int girar(int s, int p){
for(int viz : adj[s]){
if(sub[viz] == A && (qtdb[s]-qtdb[viz]-(sub[s] == B) > 0 || qtdc[s]-qtdc[viz]-(sub[s] == C) > 0)){
marcar(viz,s,marc[0]);
int cur = s, pai = -1;
while(cur == s || (sub[cur] != B && sub[cur] != C) ){
for(int viz : adj[cur]){
if(viz != pai && res[viz] == 0 && (qtdb[viz] > 0 || qtdc[viz] > 0)){pai = cur; cur = viz; break;}
}
}
if(sub[cur] == B){marcar(cur,pai,marc[1]); marcar(s,-1,marc[2]);}
else {marcar(cur,pai,marc[2]); marcar(s,-1,marc[1]);}
return viz;
}
}
for(int viz : adj[s])
if(viz != p){
qtdb[s] -= qtdb[viz]+(sub[s] == B); qtdc[s] -= qtdc[viz]+(sub[s] == C); sub[s] -= sub[viz];
sub[viz] += sub[s]; qtdb[viz] += qtdb[s]+(sub[viz]==B); qtdc[viz] += qtdc[s]+(sub[viz]==C);
int x = girar(viz,s);
if(x != -1)return x;
qtdb[viz] -= qtdb[s]+(sub[viz]==B); qtdc[viz] -= qtdc[s]+(sub[viz]==C); sub[viz] -= sub[s];
sub[s] += sub[viz]; qtdb[s] += qtdb[viz]+(sub[s] == B); qtdc[s] += qtdc[viz]+(sub[s] == C);
}
return -1;
}
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]);
}
marc[0] = 1; marc[1] = 2; marc[2] = 3; A = a; B = b; C = c;
dfsIni(0,-1);
int x = girar(0,-1);
if(x != -1)return res;
marc[0] = 2; marc[1] = 1; marc[2] = 3; A = b; B = a; C = c;
dfsIni(0,-1);
x = girar(0,-1);
if(x != -1)return res;
marc[0] = 3; marc[1] = 2; marc[2] = 1; A = c; B = b; C = a;
dfsIni(0,-1);
x = girar(0,-1);
if(x != -1)return res;
if(x == -1){
for(int i = 0; i < n; i++)res[i] = 0;
}
return res;
}
