#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vim;
vim V[100010], W[100010];
vim C[100010], par;
int chk[100010];
pair<int,int> pi[3];
int N, Ctd;
vim ans;
int chkans[100010];
void mst(int lev)
{
chk[lev]=1;
for (int i:V[lev]) {
if (!chk[i]) {
par[i]=lev;
C[lev].push_back(i);
mst(i);
}
}
}
int cent(int lev)
{
vector<int> Cs;
for (int i:C[lev]) {
Cs.push_back(cent(i));
}
int ret=0, flag=0;
for (int i:Cs) {
ret+=i;
if (i>N/2) flag=1;
}
if (N-ret-1>N/2) flag=1;
if (!flag) Ctd=lev;
return ret+1;
}
void dfs(int lev)
{
chk[lev]=1;
for (int i:C[lev]) {
if (!chk[i]) {
W[lev].push_back(i);
W[i].push_back(lev);
dfs(i);
}
}
if (!chk[par[lev]]) {
W[lev].push_back(par[lev]);
W[par[lev]].push_back(lev);
dfs(par[lev]);
}
}
int gC(int lev){
chk[lev]=1;
int ret=0;
for (int i:W[lev]) {
if (!chk[i]) ret+=gC(i);
}
return ret+1;
}
void GA1(int st, int sw)
{
if (sw==0) {
if (!pi[0].first) return ;
chk[st]=1;
chkans[st]=pi[0].second+1;
pi[0].first--;
for (int i:W[st]) {
if (!chk[i]) {
GA1(i, sw);
}
}
}
if (sw==1) {
if (!pi[1].first) return ;
chk[st]=1;
chkans[st]=pi[1].second+1;
pi[1].first--;
for (int i:W[st]) {
if (!chk[i]) {
GA1(i, sw);
}
}
}
if (sw==2) {
for (int i=0; i<N; i++) if (!chkans[i]) chkans[i]=pi[2].second+1;
for (int i=0; i<N; i++) ans.push_back(chkans[i]);
}
}
int dfs1(int lev)
{
chk[lev]=1;
int ret=1;
for (int i:V[lev]) {
if (!chk[i]) {
ret+=dfs1(i);
}
}
return ret;
}
void dfs2(int lev)
{
if (!pi[0].first) return ;
chk[lev]=1;
chkans[lev]=pi[0].second;
pi[0].first--;
for (int i:V[lev]) {
if (!chk[i]&&i!=Ctd) dfs2(i);
}
}
void dfs3(int lev)
{
if (!pi[1].first) return ;
chk[lev]=1;
chkans[lev]=pi[1].second;
pi[1].first--;
for (int i:V[lev]) {
if (!chk[i]) dfs3(i);
}
}
void dfs4()
{
int i, j=0;
for (i=0; i<N; i++) {if (!chk[i]) {chkans[i]=pi[2].second; j++;}}
for (i=0; i<N; i++) ans.push_back(chkans[i]+1);
if (j!=pi[2].first) {
printf("%d", 1/0);
}
}
int GA2()
{
int i, ret, fl=0;
memset(chk, 0, sizeof(chk));
chk[Ctd]=1;
for (i=0; i<N; i++) {
if (i!=Ctd&&!chk[i]) {
ret=dfs1(i);
if (ret>=pi[0].first) {
memset(chk, 0, sizeof(chk));
dfs2(i);
dfs3(Ctd);
dfs4();
fl=1;
break;
}
}
}
if (!fl) return -1;
return 0;
}
vim IMPOSSIBLE()
{
vim ret;
for (int i=0; i<N; i++) ret.push_back(0);
//if (ret.size()!=N) assert(false);
return ret;
}
vim find_split(int n, int a, int b, int c, vim p, vim q) {
N=n;
par.resize(n);
pi[0]={a,0}; pi[1]={b,1}; pi[2]={c,2};
sort(pi,pi+3);
int i;
for (i=0; i<p.size(); i++) {
V[p[i]].push_back(q[i]);
V[q[i]].push_back(p[i]);
}
mst(0);
cent(0);
memset(chk, 0, sizeof(chk));
dfs(Ctd);
memset(chk, 0, sizeof(chk));
chk[Ctd]=1;
vim CtdV;
for (int j:W[Ctd]) CtdV.push_back(gC(j));
memset(chk, 0, sizeof(chk));
chk[Ctd]=1;
for (i=0; i<CtdV.size(); i++) {
if (CtdV[i]>=pi[0].first){
GA1(W[Ctd][i], 0);
GA1(Ctd, 1);
GA1(0, 2);
if (ans.size()!=N) assert(false);
return ans;
}
}
if (GA2()==-1) {
return IMPOSSIBLE();
}
else {
//if (ans.size()!=N) assert(false);
return ans;
}
}
