#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,N, marc[3], atual;
void dfsIni(int s, int p){
sub[s] = 1; qtdb[s] = 0; qtdc[s] = 0;
for(int i = 0; i < adj[s].size(); i++)
if(adj[s][i] != p){
dfsIni(adj[s][i],s);
sub[s] += sub[adj[s][i]];
qtdb[s] += qtdb[adj[s][i]];
qtdc[s] += qtdc[adj[s][i]];
}
if(sub[s] == B)qtdb[s]++;
if(sub[s] == C)qtdc[s]++;
}
void marcar(int s, int p){
res[s] = atual;
for(int i = 0; i < adj[s].size(); i++)
if(adj[s][i] != p && res[adj[s][i]] == 0)marcar(adj[s][i],s);
}
int girar(int s, int p){
for(int i = 0; i < adj[s].size(); i++){
if(sub[adj[s][i]] == A && (qtdb[s]-qtdb[adj[s][i]]-(sub[s] == B) > 0 || qtdc[s]-qtdc[adj[s][i]]-(sub[s] == C) > 0)){
//cerr<<s<<" "<<adj[s][i]<<" "<<sub[s]<<" "<<sub[adj[s][i]]<<" | "<<A<<" "<<B<<" "<<C<<"\n";
//cerr<<qtdb[s]<<" "<<qtdb[adj[s][i]]<<" "<<qtdc[s]<<" "<<qtdc[adj[s][i]]<<"\n";
atual = marc[0]; marcar(adj[s][i],s);
int cur = s, pai = -1;
int temp = 0;
while(cur == s || (sub[cur] != B && sub[cur] != C) ){
//cerr<<cur<<"\n";
for(int j = 0; j < adj[cur].size(); j++){
//cerr<<qtdb[adj[cur][j]]<<" "<<qtdc[adj[cur][j]]<<"\n";
if(adj[cur][j] != pai && res[adj[cur][j]] == 0 && (qtdb[adj[cur][j]] > 0 || qtdc[adj[cur][j]] > 0)){pai = cur; cur = adj[cur][j]; break;}
}
temp++;
assert(temp <= N);
}
if(sub[cur] == B){atual = marc[1]; marcar(cur,pai); atual = marc[2]; marcar(s,-1);}
else {atual = marc[2]; marcar(cur,pai); atual = marc[1]; marcar(s,-1);}
return adj[s][i];
}
}
for(int i = 0; i < adj[s].size(); i++)
if(adj[s][i] != p){
qtdb[s] -= qtdb[adj[s][i]]+(sub[s] == B); qtdc[s] -= qtdc[adj[s][i]]+(sub[s] == C);
sub[s] -= sub[adj[s][i]];
qtdb[s] += (sub[s] == B); qtdc[s] += (sub[s] == C);
qtdb[adj[s][i]] -= (sub[adj[s][i]] == B); qtdc[adj[s][i]] -= (sub[adj[s][i]] == C);
sub[adj[s][i]] += sub[s];
qtdb[adj[s][i]] += qtdb[s]+(sub[adj[s][i]]==B); qtdc[adj[s][i]] += qtdc[s]+(sub[adj[s][i]]==C);
int x = girar(adj[s][i],s);
if(x != -1)return x;
qtdb[adj[s][i]] -= qtdb[s]+(sub[adj[s][i]]==B); qtdc[adj[s][i]] -= qtdc[s]+(sub[adj[s][i]]==C);
sub[adj[s][i]] -= sub[s];
qtdb[adj[s][i]] += (sub[adj[s][i]] == B); qtdc[adj[s][i]] += (sub[adj[s][i]] == C);
qtdb[s] -= (sub[s] == B); qtdc[s] -= (sub[s] == C);
sub[s] += sub[adj[s][i]];
qtdb[s] += qtdb[adj[s][i]]+(sub[s] == B); qtdc[s] += qtdc[adj[s][i]]+(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); N = n;
for(int i = 0; i < n; i++)adj[i].clear();
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;
}
