#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
int n,m,sz[MAXN];
pair<int,int> s[3];
vector<int> v[MAXN],tree[MAXN],ans;
int sol[MAXN],dep[MAXN],low[MAXN];
bool vis[MAXN],used[MAXN],ok;
bool check(int x,int y){
return x>=s[0].first and y>=s[1].first;
}
void subtree(int x,int id){
if(s[id].first==0)return;
used[x]=true;
sol[x]=s[id].second;
s[id].first--;
for(int i:tree[x])subtree(i,id);
}
void mark(int x,int id){
if(s[id].first==0)return;
used[x]=true;
sol[x]=s[id].second;
s[id].first--;
for(int i:v[x]){
if(used[i])continue;
mark(i,id);
}
}
bool dfs(int x,int p){
dep[x]=dep[p]+1; low[x]=dep[x];
vis[x]=true; sz[x]=1;
for(int i=0;i<v[x].size();i++){
if(!vis[v[x][i]]){
if(dfs(v[x][i],x))return true;
tree[x].push_back(v[x][i]);
sz[x]+=sz[v[x][i]];
low[x]=min(low[x],low[v[x][i]]);
}else if(v[x][i]!=p){
low[x]=min(low[x],dep[v[x][i]]);
}
}
vector< pair<int,int> > conn,cut;
int sumconn=0,sumcut=0;
for(int i:tree[x]){
if(low[i]<=dep[x]){
conn.push_back({sz[i],i});
sumconn+=sz[i];
}else{
cut.push_back({sz[i],i});
sumcut+=sz[i];
}
}
sort(cut.begin(),cut.end());
sort(conn.begin(),conn.end());
/// one vertex ///
for(int i:tree[x]){
if(check(sz[i],n-sz[i])){
subtree(i,0); mark(x,1);
return true;
}
if(check(n-sz[i],sz[i])){
subtree(i,1); mark(x,0);
return true;
}
}
/// a set of cut vertices ///
int pt=0,sum=1;
for(int i=0;i<cut.size();i++){
while(pt<cut.size() and sum<s[0].first){
sum+=cut[pt].first; pt++;
}
if(check(sum,n-sz[x]+sumconn)){
sol[x]=s[0].second; s[0].first--; used[x]=true;
for(int e=i;e<pt;e++)subtree(cut[e].second,0);
mark(p,1);
return true;
}
if(check(n-sz[x]+sumconn,sum)){
sol[x]=s[1].second; s[1].first--; used[x]=true;
for(int s=i;s<pt;s++)subtree(cut[s].second,1);
mark(p,0);
return true;
}
sum-=cut[i].first;
}
/// all cut vertices + a set of connected vertices ///
sum=sumcut+1; pt=0;
for(int i=0;i<conn.size();i++){
while((pt<conn.size() and sum<s[0].first) or pt==i){
sum+=conn[pt].first; pt++;
}
if(check(sum,n-sum)){
sol[x]=s[0].second; s[0].first--; used[x]=true;
for(int s=0;s<cut.size();s++)subtree(cut[s].second,0);
for(int s=i;s<pt;s++)subtree(conn[s].second,0);
mark(p,1); ok=true;
return true;
}
if(check(n-sum,sum)){
sol[x]=s[1].second; s[1].first--; used[x]=true;
for(int s=0;s<cut.size();s++)subtree(cut[s].second,1);
for(int s=i;s<pt;s++)subtree(conn[s].second,1);
mark(p,0); ok=true;
return true;
}
sum-=conn[i].first;
}
/// hopefully all cases
return false;
}
vector<int> find_split(int N, int A, int B, int C,vector<int> p,vector<int> q){
n=N; m=int(p.size());
s[0]={A,1}; s[1]={B,2}; s[2]={C,3};
sort(s,s+3);
for(int i=1;i<=m;i++){
v[p[i-1]+1].push_back(q[i-1]+1);
v[q[i-1]+1].push_back(p[i-1]+1);
}
ans.resize(n);
if(!dfs(1,0))return ans;
if((s[0].first>0 or s[1].first>0) and ok)cout<<1/0;
for(int i=1;i<=n;i++){
if(sol[i]==0)sol[i]=s[2].second;
}
for(int i=1;i<=n;i++)ans[i-1]=sol[i];
return ans;
}
/*int main(){
ans=find_split(9, 4, 2, 3, {0, 0, 0, 0, 0, 0, 1, 3, 4, 5},{1, 2, 3, 4, 6, 8, 7, 7, 5, 6});
for(int i:ans){
cout<<i<<" ";
}
return 0;
}*/
