#include "split.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("fast-math")
//#pragma GCC optimize ("unroll-loops")
using namespace std;
typedef pair<int,int> pii;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int n,m;
int take[5],ord[5];
vector<int> sol;
bool byval(int a,int b)
{
return take[a]<take[b];
}
vector<int> kids[100005],edges[100005];
vector<int> dsu[100005];
bool rebel[100005];
int comp[100005];
vector<pii> g;
vector<int> linie;
int par[100005];
bool use[100005];
vector<int> nodes;
int nr[100005];
int niv[100005],nivmin[100005];
int part[100005];
void dfs(int nod)
{
nr[nod]=1;
use[nod]=1;
nivmin[nod]=niv[nod];
for(int i:edges[nod])
{
if(i==par[nod])
continue;
if(!use[i])
{
niv[i]=niv[nod]+1;
par[i]=nod;
dfs(i);
kids[nod].push_back(i);
nr[nod]+=nr[i];
nivmin[nod]=min(nivmin[nod],nivmin[i]);
}
else
nivmin[nod]=min(nivmin[nod],niv[i]);
}
}
bool valid(int nod)
{
if(nr[nod]<take[ord[1]])
return 0;
for(int i:kids[nod])
if(nr[i]>=take[ord[1]])
return 0;
return 1;
}
bool good(int lg1,int lg2)
{
return min(lg1,lg2)>=take[ord[1]]&&max(lg1,lg2)>=take[ord[2]];
}
void put(int nod,int x)
{
part[nod]=x;
for(int i:kids[nod])
if(part[i]==0)
put(i,x);
}
void build(int nod,int x)
{
nodes.push_back(nod);
use[nod]=1;
for(int i:edges[nod])
if(part[i]==x&&!use[i])
build(i,x);
}
void go(int nod,int x)
{
part[nod]=x;
for(int i:edges[nod])
if(part[i]==0)
go(i,x);
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q)
{
n=N;
take[1]=A;
take[2]=B;
take[3]=C;
ord[1]=1;
ord[2]=2;
ord[3]=3;
sort(ord+1,ord+4,byval);
sol.resize(n);
m=p.size();
for(int i=0;i<n;i++)
{
par[i]=-1;
comp[i]=i+1;
}
for(int i=0;i<p.size();i++)
{
int a,b;
a=p[i];
b=q[i];
edges[a].push_back(b);
edges[b].push_back(a);
}
niv[0]=1;
dfs(0);
for(int v=0;v<n;v++)
if(valid(v))
{
vector<int> rebeli;
int lg1=nr[v],lg2=n-nr[v];
for(int i=0;i<kids[v].size();i++)
{
int u=kids[v][i];
rebel[u]=0;
if(nivmin[u]<niv[v]&&lg1-nr[u]>=take[ord[1]])
{
lg1-=nr[u];
rebeli.push_back(u);
rebel[u]=1;
lg2+=nr[u];
}
}
if(good(lg1,lg2))
{
for(int i=0;i<n;i++)
use[i]=0;
part[v]=1;
for(int i:kids[v])
if(!rebel[i])
put(i,1);
int z=0;
for(int i=0;i<n;i++)
if(part[i]==0)
{
z=i;
break;
}
int c1=ord[1];
int c2=ord[2];
if(lg1>lg2)
{
swap(c1,c2);
}
go(z,2);
nodes.clear();
build(v,1);
for(int i=0;i<take[c1];i++)
sol[nodes[i]]=c1;
nodes.clear();
int r=-1;
for(int i=0;i<n;i++)
if(part[i]==2)
{
r=i;
break;
}
build(r,2);
for(int i=0;i<take[c2];i++)
sol[nodes[i]]=c2;
for(int i=0;i<n;i++)
if(sol[i]==0)
sol[i]=ord[3];
return sol;
}
}
return sol;
}
