#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
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<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;
return true;
}
ll root(ll i){
if(par[i]==-1)return i;
return root(par[i]);
}
};
long double time_start;
long double gettime(){
return (clock()-time_start)/CLOCKS_PER_SEC;
}
vector<int> find_split(int n, int A, int B, int C, vector<int> p, vector<int> q) {
time_start=clock();
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> kan(n,false);
vi id_ver(n),id_edge(m);
ll num_kan=0,num_=0;
function<void(ll,ll,ll)> dfs1=[&](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){
dfs1(x.fi,i,d+1);
chmin(lk[i],lk[x.fi]);
}
else chmin(lk[i],dep[x.fi]);
}
};dfs1(0,-1,0);
function<void(ll,ll)> dfs2=[&](ll i,ll e){
if(i==0){
vi al;
for(auto x:g1[i]){
if(par[x.fi]==i){
id_edge[x.se]=num_++;
al.pb(id_edge[x.se]);
dfs2(x.fi,x.se);
}
}
if(al.size()>1)kan[i]=true;
else id_ver[i]=al[0];
return;
}
for(auto x:g1[i])if(x.fi!=par[i]){
if(par[x.fi]==i){
if(lk[x.fi]>=dep[i]){
kan[i]=true;
id_edge[x.se]=num_++;
}
else id_edge[x.se]=id_edge[e];
dfs2(x.fi,x.se);
}
else if(dep[x.fi]<dep[i])id_edge[x.se]=id_edge[e];
}
if(!kan[i])id_ver[i]=id_edge[e];
};dfs2(0,-1);
rep(i,n)if(kan[i])id_ver[i]=(num_kan++)+num_;
ll c=num_+num_kan;
vvi g2(c);
// outv(id_ver);outv(id_edge);
rep(i,m){
if(id_edge[i]!=id_ver[p[i]]){
g2[id_edge[i]].pb(id_ver[p[i]]);
g2[id_ver[p[i]]].pb(id_edge[i]);
}
if(id_edge[i]!=id_ver[q[i]]){
g2[id_edge[i]].pb(id_ver[q[i]]);
g2[id_ver[q[i]]].pb(id_edge[i]);
}
}
rep(i,c)dupli(g2[i]);
queue<ll> que;
vi deg(c);
rep(i,c)deg[i]=g2[i].size();
vvi gr1(c);
rep(i,n)gr1[id_ver[i]].pb(i);
rep(i,c)if(gr1[i].size()<k&°[i]==1)que.push(i);
vector<bool> done(c,false);
while(!que.empty()){
ll t=que.front();que.pop();
for(ll x:g2[t])if(!done[x]){
if(gr1[x].size()<gr1[t].size())swap(gr1[x],gr1[t]);
for(ll y:gr1[t])gr1[x].pb(y);
done[t]=true;
deg[x]--;
if(deg[x]==1&&gr1[x].size()<k)que.push(x);
}
}
vi al;
rep(i,c)if(!done[i])al.pb(i);
auto sol=[&](ll sz,vector<bool> flag){
ll i=0;
while(!flag[i])i++;
flag[i]=false;
vi res;
function<void(ll)> dfs_=[&](ll cur){
if(res.size()==sz)return;
res.pb(cur);
for(auto x:g1[cur])if(flag[x.fi]){
flag[x.fi]=false;
dfs_(x.fi);
if(res.size()==sz)return;
}
};dfs_(i);
return res;
};
if(al.size()>1){
ll t=0;
while(deg[al[t]]!=1||gr1[al[t]].size()>n/2)t++;
t=al[t];
vi va,vb,vc;
vector<bool> fa(n,false),fb(n,false),fc(n,true);
for(ll x:gr1[t])fa[x]=true;
rep(i,n)if(!fa[i])fb[i]=true;
va=sol(k,fa);vb=sol(n-max({A,B,C})-k,fb);
// assert(va.size()==k);
// assert(vb.size()==n-max({A,B,C})-k);
for(ll x:va)fc[x]=false;
for(ll x:vb)fc[x]=false;
rep(i,n)if(fc[i])vc.pb(i);
// outv(va);outv(vb);outv(vc);
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;
}
ll rt=al[0];
vector<bool> seen(n,false);
rep(i,n)if(id_ver[i]==rt)seen[i]=true;
vvi tmp(n);
rep(i,n)if(id_ver[i]==rt){
function<void(ll)> dfs=[&](ll cur){
tmp[i].pb(cur);
for(auto x:g1[cur])if(!seen[x.fi]){
seen[x.fi]=true;
dfs(x.fi);
}
};dfs(i);
}
rep(i,n)if(tmp[i].size()>n-k)return res;
{
vi sp,id_sp(n,-1);
ll N=0;
rep(i,n)if(id_ver[i]==rt){
sp.pb(i);id_sp[i]=N++;
}
vvi g(N,vi(N));
rep(i,n)for(auto x:g1[i]){
if(id_sp[i]!=-1&&id_sp[x.fi]!=-1)g[id_sp[i]].pb(id_sp[x.fi]);
}
vector<bool> done(N,false);
done[0]=true;
ll cur=gr1[sp[0]].size();
while(cur<k){
vi zan,id_zan(N,-1);
ll Z=0;
rep(i,N)if(!done[i]){
zan.pb(i);id_zan[i]=Z++;
}
vvi g_(Z,vi(Z));
rep(i,N)for(auto x:g[i])if(id_zan[i]!=-1&&id_zan[x]!=-1)g_[id_zan[i]].pb(id_zan[x]);
vector<bool> ok(Z,false);
rep(i,Z)for(auto x:g[zan[i]])if(id_zan[x]==-1)ok[i]=true;
vi lk(Z,inf),dep(Z,-1),par(Z);
function<void(ll,ll,ll)> dfs1=[&](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){
dfs1(x.fi,i,d+1);
chmin(lk[i],lk[x.fi]);
}
else chmin(lk[i],dep[x.fi]);
}
};dfs1(0,-1,0);
vector<bool> kan(Z,false);
function<void(ll,ll)> dfs2=[&](ll i,ll e){
if(i==0){
ll c=0;
for(auto x:g1[i]){
if(par[x.fi]==i){
c++;
dfs2(x.fi,x.se);
}
}
if(c>1)kan[i]=true;
return;
}
for(auto x:g1[i])if(x.fi!=par[i]){
if(par[x.fi]==i){
if(lk[x.fi]>=dep[i]){
kan[i]=true;
}
dfs2(x.fi,x.se);
}
}
};dfs2(0,-1);
rep(i,Z){
if(ok[i]&&!kan[i]){
done[zan[i]]=true;cur+=gr1[sp[zan[i]]].size();break;
}
}
}
vi va,vb,vc;
ll c=0;
vector<bool> fa(n,false),fb(n,false),fc(n,true);
rep(i,N)if(done[i])for(ll x:gr1[sp[i]]){
fa[x]=true;c++;
}
rep(i,n)if(!fa[i])fb[i]=true;
if(c>n/2)swap(fa,fb);
va=sol(k,fa);vb=sol(n-max({A,B,C})-k,fb);
// assert(va.size()==k);
// assert(vb.size()==n-max({A,B,C})-k);
for(ll x:va)fc[x]=false;
for(ll x:vb)fc[x]=false;
rep(i,n)if(fc[i])vc.pb(i);
// outv(va);outv(vb);outv(vc);
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;
}
while(true){
vi ord(m);
rep(i,m)ord[i]=i;
random_shuffle(all(ord));
UF uf(n);
vvi g(n);
for(ll i:ord)if(uf.merge(p[i],q[i])){
g[p[i]].pb(q[i]);g[q[i]].pb(p[i]);
}
vi sub(n,1),par(n,-1),al;
function<ll(ll,ll)> dfs=[&](ll i,ll p){
al.pb(i);
par[i]=p;
for(ll x:g[i])if(x!=p){
sub[i]+=dfs(x,i);
}
return sub[i];
};dfs(0,-1);
rep(i,n)if(sub[i]>=k&&sub[i]<=n-k){
al=vi(0);dfs(i,par[i]);
vi va,vb,vc;
vector<bool> fa(n,false),fb(n,false),fc(n,true);
for(ll x:al)fa[x]=true;
rep(i,n)if(!fa[i])fb[i]=true;
if(al.size()>n/2)swap(fa,fb);
va=sol(k,fa);vb=sol(n-max({A,B,C})-k,fb);
// assert(va.size()==k);
// assert(vb.size()==n-max({A,B,C})-k);
for(ll x:va)fc[x]=false;
for(ll x:vb)fc[x]=false;
rep(i,n)if(fc[i])vc.pb(i);
// outv(va);outv(vb);outv(vc);
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;
}
