#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
// typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define fi first
#define se second
#define pb emplace_back
template<class T> void out(T a){cout<<a<<endl;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
const ll inf=1001001001;
struct UF{
vi par,sz;
UF(ll n):par(n,-1),sz(n,1){}
bool merge(ll a,ll b){
a=root(a);b=root(b);
if(a==b)return false;
if(sz[a]<sz[b])swap(a,b);
sz[a]+=sz[b];par[b]=a;
}
ll root(ll i){
if(par[i]==-1)return i;
return root(par[i]);
}
};
vector<int> find_split(int n, int A, int B, int C, vector<int> p, vector<int> q) {
ll k=min({A,B,C});
vector<int> res(n);
vvp g1(n);
ll m=p.size();
rep(i,m){
g1[p[i]].pb(q[i],i);
g1[q[i]].pb(p[i],i);
}
vi lk(n,inf),dep(n,-1),par(n);
vector<bool> bridge(m,false);
UF uf(n);
function<void(ll,ll,ll)> dfs=[&](ll i,ll p,ll d){
par[i]=p;dep[i]=d;
for(auto x:g1[i])if(x.fi!=p){
if(dep[x.fi]==-1){
dfs(x.fi,i,d+1);
chmin(lk[i],lk[x.fi]);
if(lk[x.fi]>dep[i])bridge[x.se]=true;
else uf.merge(i,x.fi);
}
else{
chmin(lk[i],dep[x.fi]);
}
}
};dfs(0,-1,0);
vvp g2(n);
rep(i,m)if(bridge[i]){
ll a=uf.root(p[i]),b=uf.root(q[i]);
g2[a].pb(b,q[i]);g2[b].pb(a,p[i]);
}
queue<ll> que;
vi deg(n);
rep(i,n)deg[i]=g2[i].size();
vvi gr1(n);rep(i,n)gr1[uf.root(i)].pb(i);
rep(i,n)if(gr1[i].size()>0&&gr1[i].size()<k&°[i]==1)que.push(i);
while(!que.empty()){
ll t=que.front();que.pop();
for(auto x:g2[t])if(gr1[x.fi].size()>0){
if(gr1[x.fi].size()<gr1[t].size())swap(gr1[x.fi],gr1[t]);
for(ll y:gr1[t])gr1[x.fi].pb(y);
gr1[t].clear();
deg[x.fi]--;
if(deg[x.fi]==1&&gr1[x.fi].size()<k)que.push(x.fi);
}
}
vi al;
rep(i,n)if(gr1[i].size()>0)al.pb(i);
if(al.size()>1){
ll t=0;
while(deg[al[t]]!=1)t++;
t=al[t];
vi va,vb,vc;
for(ll x:gr1[t])va.pb(x);
vector<bool> used(n,false);
for(ll x:va)used[x]=true;
rep(i,n)if(!used[i])vb.pb(i);
if(va.size()>vb.size())swap(va,vb);
while(va.size()>k){
vc.pb(va.back());va.pop_back();
}
while(vb.size()>max({A,B,C})-k){
vc.pb(vb.back());vb.pop_back();
}
if(A!=va.size())swap(va,vb);
if(A!=va.size())swap(va,vc);
if(B!=vb.size())swap(vb,vc);
for(ll x:va)res[x]=1;
for(ll x:vb)res[x]=2;
for(ll x:vc)res[x]=3;
return res;
}
return res;
}
