#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
int n,m,li[MAXN],tim,sz[MAXN];
pair<int,int> s[3];
vector<int> v[MAXN],ans,tree[MAXN];
int in[MAXN];
int sol[MAXN];
bool vis[MAXN];
void subtree(int x,int id){
if(s[id].first==0)return;
vis[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;
vis[x]=true;
sol[x]=s[id].second;
s[id].first--;
for(int i:v[x]){
if(vis[i])continue;
mark(i,id);
}
}
bool dfs(int x,int p){
li[x]=tim; sz[x]=1; in[x]=1;
for(int i=0;i<v[x].size();i++){
if(li[v[x][i]]==tim)continue;
tree[x].push_back(v[x][i]);
if(dfs(v[x][i],x))return true;
sz[x]+=sz[v[x][i]];
}
in[x]=2;
if(sz[x]>=s[0].first and n-sz[x]>=s[1].first){
subtree(x,0);
mark(p,1);
return true;
}
if(sz[x]>=s[1].first and n-sz[x]>=s[0].first){
subtree(x,1);
mark(p,0);
return true;
}
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);
for(int i=1;i<=n;i++){
for(int f=1;f<=n;f++){
tree[f].clear(); in[f]=0;
random_shuffle(v[f].begin(),v[f].end());
}
tim++;
if(dfs(i,0))break;
if(i==n)return ans;
}
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;
}*/
