#include<bits/stdc++.h>
#include "split.h"
using namespace std;
vector<int>D[100009];
int Deep[100009];
int NadMna[100009];
bool zaj[100009];
int n,m,aa,bb,cc;
vector<int>Odp;
vector<int>A,B;
int ziom=-1;
void DFS3(int v)
{
if(zaj[v]){return;}
zaj[v]=1;
B.push_back(v);
for(int som : D[v])
{
if(Deep[som]<=Deep[v]){continue;}
DFS3(som);
}
}
void DFS2(int v, bool stan)
{
zaj[v]=1;
if(stan==0)
{
bool cv=0;
for(int som : D[v])
{
if(Deep[som]<Deep[ziom]){cv=1;break;}
}
if(cv&&NadMna[ziom]-NadMna[v]>=aa)
{
stan=1;
NadMna[ziom]-=NadMna[v];
}
}
if(stan==0){A.push_back(v);}
else{B.push_back(v);}
for(int som : D[v])
{
if(zaj[som]||Deep[som]!=Deep[v]+1){continue;}
DFS2(som,stan);
}
}
void DFS(int v)
{
NadMna[v]=1;
for(int som : D[v])
{
if(Deep[som]!=0){continue;}
Deep[som]=Deep[v]+1;
DFS(som);
NadMna[v]+=NadMna[som];
}
if(ziom==-1&&NadMna[v]>=aa){ziom=v;}
}
vector<int>find_split(int N, int aaa, int bbb, int ccc, vector<int>E1, vector<int>E2)
{
aa=aaa;
bb=bbb;
cc=ccc;
vector<pair<int,int>>H={{aaa,1},{bbb,2},{ccc,3}};
sort(H.begin(),H.end());
aa=H[0].first;
bb=H[1].first;
cc=H[2].first;
n=N;
m=(int)E1.size();
Odp.resize(n);
for(int i=0;i<m;i++)
{
int a=E1[i],b=E2[i];
D[a].push_back(b);
D[b].push_back(a);
}
Deep[0]=1;
DFS(0);
DFS2(ziom,0);
memset(zaj,0,sizeof(zaj));
for(int u : A){zaj[u]=1;}
DFS3(0);
if((int)B.size()>=bb)
{
for(int i=0;i<aa;i++){Odp[A[i]]=1;}
for(int i=0;i<bb;i++){Odp[B[i]]=2;}
}
else if((int)B.size()>=aa&&(int)A.size()>=bb)
{
for(int i=0;i<bb;i++){Odp[A[i]]=2;}
for(int i=0;i<aa;i++){Odp[B[i]]=1;}
}
else
{
for(int i=0;i<n;i++){Odp[i]=0;}
return Odp;
}
for(int i=0;i<n;i++)
{
if(Odp[i]==0){Odp[i]=H[2].second;}
else{Odp[i]=H[Odp[i]-1].second;}
}
return Odp;
}
