#include "split.h"
#include <bits/stdc++.h>
using namespace std;
int dsu[100010];
int prt(int n){
if (dsu[n]==n) return n;
return dsu[n]=prt(dsu[n]);
}
void unn(int u,int v){
dsu[prt(u)]=dsu[prt(v)];
}
vector <int> g[100010];
int sz[100010];
void dfs(int cur,int prv){
sz[cur]=1;
for (int i:g[cur]){
if (i==prv) continue;
dfs(i,cur);
sz[cur]+=sz[i];
}
}
int getcen(int cur,int prv,int n){
for (int i:g[cur]){
if (i==prv) continue;
if (2*sz[i]>n) return getcen(i,cur,n);
}
return cur;
}
int belong[100010],siz[100010];
void dfs2(int cur,int prv,int lab){
belong[cur]=lab;
siz[lab]++;
for (int i:g[cur]){
if (i==prv) continue;
dfs2(i,cur,lab);
}
}
vector <int> ans;
vector <pair <int,int> > ord;
void complete(int r){
queue <int> q;
q.push(r);
ans[r]=ord[1].second;
int cnt=1;
while (cnt<ord[1].first){
int tp=q.front(); q.pop();
for (int i:g[tp]){
if (ans[i]) continue;
cnt++;
ans[i]=ord[1].second;
q.push(i);
if (cnt==ord[1].first) break;
}
}
for (int i=0; i<ans.size(); i++){
if (!ans[i]) ans[i]=ord[2].second;
}
}
vector <int> find_split(int n,int a,int b,int c,vector <int> p,vector <int> q){
ord.push_back({a,1}); ord.push_back({b,2}); ord.push_back({c,3});
sort(ord.begin(),ord.end());
for (int i=0; i<n; i++) dsu[i]=i;
vector <int> rem[n];
for (int i=0; i<p.size(); i++){
if (prt(p[i])==prt(q[i])){
rem[p[i]].push_back(q[i]);
rem[q[i]].push_back(p[i]);
continue;
}
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
unn(p[i],q[i]);
}
ans.resize(n);
dfs(0,-1);
c=getcen(0,-1,n);
for (int i=0; i<n; i++) belong[i]=-1;
for (int i:g[c]) dfs2(i,c,i);
bool done=0;
for (int i=0; i<n; i++){
if (siz[i]>=ord[0].first){
queue <int> q;
q.push(i);
ans[i]=ord[0].second;
int cnt=1;
while (cnt<ord[0].first){
int tp=q.front(); q.pop();
for (int j:g[tp]){
if (ans[j]||belong[j]!=belong[i]) continue;
q.push(j);
ans[j]=ord[0].second;
cnt++;
if (cnt==ord[0].first) break;
}
}
done=1;
break;
}
}
if (!done){
bool visited[n];
for (int i=0; i<n; i++) visited[i]=0;
visited[c]=1;
for (int i=0; i<n; i++){
if (visited[i]) continue;
deque <int> q;
vector <int> vec;
int cnt=0;
q.push_back(i);
while (!q.empty()&&cnt<ord[0].first){
int tp=q.front(); q.pop_front();
if (visited[tp]) continue;
visited[tp]=1;
vec.push_back(i); cnt++;
if (cnt==ord[0].first) break;
for (int j:g[tp]){
if (!visited[j]) q.push_front(j);
}
for (int j:rem[tp]){
if (!visited[j]) q.push_back(j);
}
}
if (cnt==ord[0].first){
for (int j:vec) ans[j]=ord[0].second;
done=1;
break;
}
}
}
if (done){
complete(c);
int cnt[4]={0,0,0,0};
for (int i:ans) cnt[i]++;
assert(cnt[1]==a&&cnt[2]==b);
}
return ans;
}
