#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;
int ileA=0,ileB=0;
vector<int>Odp;
int ziom=-1;
void DFS3(int v)
{
if(zaj[v]){return;}
zaj[v]=1;
if(ileB<bb)
{
Odp[v]=2;
ileB++;
}
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)
{
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&&ileA<aa)
{
Odp[v]=1;
ileA++;
}
else if(stan==1&&ileB<bb)
{
Odp[v]=2;
ileB++;
}
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);
DFS3(0);
if(ileB<bb)
{
for(int i=0;i<n;i++){Odp[i]=0;}
}
else
{
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;
}
