#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define lowb(x) (x&(-x))
#define ALL(_x) _x.begin(),_x.end()
#define pii pair<int,int>
#define f first
#define s second
#define SORT_UNIQUE(x) sort(ALL(x)),x.erase(unique(ALL(x)),x.end())
#define MNTO(x,y) x=min(x,y)
const int maxn=1e5+5;
#define ll long long
vector<int> v[maxn];
bool vis[maxn];
vector<int> top;
int sz[maxn];
vector<int> val;
vector<int> cand;
vector<int> g[maxn];
int low[maxn],dep[maxn];
int cur=0;
int par[maxn];
int in[maxn],out[maxn];
void dfs(int u,int p){
par[u]=p;
low[u]=dep[u]=in[u]=(cur++);
vis[u]=1;
sz[u]=1;
bool ok=1;
for(int x:v[u]){
if(x==p) continue;
if(!vis[x]){
dfs(x,u);
g[u].pb(x);
sz[u]+=sz[x];
if(sz[x]>=val[0]){
ok=0;
}
MNTO(low[u],low[x]);
}
else{
MNTO(low[u],dep[x]);
}
}
if(ok and sz[u]>=val[0]) cand.pb(u);
out[u]=(cur-1);
}
bool sp[maxn];
void dfs2(int u){
sp[u]=1;
for(int x:g[u]){
dfs2(x);
}
}
//x inside a
bool ins(int x,int a){
return (in[a]<=in[x] and out[x]<=out[a]);
}
vector<int> ans;
vector<int> asd={1,2,3};
void dfs3(int u){
if(!val[1]) return;
--val[1];
ans[u]=asd[1];
for(int x:v[u]){
if(ans[x]) continue;
if(sp[x] or !ins(x,cur)){
dfs3(x);
}
}
}
void dfs4(int u){
if(!val[0]) return;
--val[0];
ans[u]=asd[0];
for(int x:g[u]){
if(sp[x]) continue;
dfs4(x);
}
}
int col[maxn];
bool cmp(int a,int b){
return val[a-1]<val[b-1];
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
REP(i,n) ans.pb(0);
REP(i,sz(p)){
v[p[i]].pb(q[i]),v[q[i]].pb(p[i]);
}
val={a,b,c};
sort(ALL(asd),cmp);
sort(ALL(val));
dfs(0,-1);
for(int x:cand){
if(!x) continue;
cur=x;
int tot=sz[x];
bool swp=0;
if(tot>=val[1]) swap(val[1],val[0]),swap(asd[0],asd[1]),swp=1;
vector<int> oth;
for(int z:g[x]){
if(low[z]>=dep[x]){
continue;
}
if(tot-sz[z]<val[0]) continue;
oth.pb(z);
tot-=sz[z];
}
if(n-tot<val[1]){
if(swp) swap(val[1],val[0]),swap(asd[0],asd[1]);
continue;
}
for(int z:oth){
dfs2(z);
}
dfs3(par[x]);
dfs4(x);
REP(i,n) if(!ans[i]) ans[i]=asd[2];
return ans;
}
return ans;
}
