#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,jakis=-1;
void DFS3(int v)
{
if(zaj[v]){return;}
zaj[v]=1;
if((int)B.size()<bb){B.push_back(v);}
for(int som : D[v])
{
if(Deep[som]!=Deep[v]+1){continue;}
DFS3(som);
}
}
void DFS2(int v, bool stan)
{
zaj[v]=1;
if(stan==0)
{
int cv=-1;
if(ziom!=v)
for(int som : D[v])
{
if(Deep[som]<Deep[ziom]){cv=som;break;}
}
if(cv!=-1&&NadMna[ziom]-NadMna[v]>=aa)
{
if(jakis==-1)
{
jakis=cv;
DFS3(jakis);
memset(zaj,0,sizeof(zaj));
for(int u : B)
{
zaj[u]=1;
}
}
if(zaj[cv])
{
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);
if(jakis==-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
{
swap(aa,bb);
swap(H[0],H[1]);
A.clear();
B.clear();
jakis=-1;
ziom=-1;
memset(zaj,0,sizeof(zaj));
memset(Deep,0,sizeof(Deep));
memset(NadMna,0,sizeof(NadMna));
Deep[0]=1;
DFS(0);
DFS2(ziom,0);
if(jakis==-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
{
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;
}
