#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> ii;
const int MX = (int)(2e5+5);
ii options[3];
int N,s[MX],par[MX],ans[MX],nb,comp,nb2,color,m;
bitset<MX> vis;
vector<int> vec[MX],G;
void dfs(int node,int p){
s[node]=1;
par[node]=p;
for(auto it:vec[node])
if(it!=p)dfs(it,node),s[node]+=s[it];
}
void trav(int node,int p,int c){
if(!nb)return;
vis[node]=1;
ans[node]=c;
nb--;
for(auto it:vec[node])
if(it!=p)trav(it,node,c);
}
void explore(int node,int p){
vis[node]=1;comp++;
for(auto it:vec[node])
if(!vis[it] && it!=p)
explore(it,node);
}
void gimme(int node,int p,int c){
if(!nb2)return;
ans[node]=c;
nb2--;
for(auto it:vec[node])
if(it!=p && !ans[it])gimme(it,node,c);
}
void dfs2(int node,int c){
if(!nb)return;
vis[node]=1;
ans[node]=c;
nb--;
for(auto it:vec[node])
if(!vis[it])dfs2(it,c);
}
void dfs3(int node){
vis[node]=1;
G.push_back(node);
for(auto it:vec[node])
if(!vis[it])dfs3(it);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
for (int i = 0; i < (int)(p.size()); ++i)
{
vec[p[i]].push_back(q[i]);
vec[q[i]].push_back(p[i]);
}
vector<int> res(n,0);
if((int)p.size()!=(n-1)){
if(a==1){
nb=min(b,c);
if(nb==b)dfs2(0,2),color=3;
else dfs2(0,3),color=2;
for (int i = 0; i < n; ++i)
if(!vis[i]){ans[i]=1;break;}
for (int i = 0; i < n; ++i)
{
if(ans[i])res[i]=ans[i];
else res[i]=color;
}
}
else{
int st=0;
for (int i = 0; i < n; ++i)
if(vec[i].size()==1){st=i;break;}
dfs3(st);
for (int i = 0; i < a; ++i)
res[G[i]]=1;
for (int i = a; i < a+b; ++i)
res[G[i]]=2;
for (int i = a+b; i < n; ++i)
res[G[i]]=3;
}
return res;
}
options[0]={a,min(b,c)},options[1]={b,min(a,c)},options[2]={c,min(a,b)};
N=n,dfs(0,0);
ii f={-1,-1};
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < 3; ++j)
if(s[i]>=options[j].fi && (n-s[i])>=options[j].se){
f={i,j};break;
}
if(f.fi!=-1)break;
}
if(f.fi==-1)return res;
else{
if(!f.se){
nb=a;
if(min(b,c)==b)nb2=b,color=2,m=3;
else nb2=c,color=3,m=2;
}
else if(f.se==1){
nb=b;
if(min(a,c)==a)nb2=a,color=1,m=3;
else nb2=c,color=3,m=1;
}
else{
nb=c;
if(min(a,b)==a)nb2=a,color=1,m=2;
else nb2=b,color=2,m=1;
}
trav(f.fi,par[f.fi],f.se+1);
for (int i = 0; i < n; ++i)
if(!vis[i]){
comp=0;
explore(i,i);
if(comp>=options[f.se].se){
gimme(i,i,color);
break;
}
}
for (int i = 0; i < n; ++i)
{
if(ans[i])res[i]=ans[i];
else res[i]=m;
}
}
return res;
}
