#pragma GCC optimize("Ofast,unroll-loops")
#include "split.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
#define N 100015
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int>g[N],tre[N],leaf1,leaf2,res;
int sz[N],A,B,C,deg[N],mx[N],n;
bool vis[N];
struct dsu{
int arr[N],sz[N];
void init(int n){
for (int i=1;i<=n;i++){
arr[i]=i; sz[i]=1;
}
}
int find(int x){
if (arr[x]==x) return x;
return arr[x]=find(arr[x]);
}
void Merge(int a,int b){
int ra=find(a),rb=find(b);
if (ra==rb) return;
if (sz[ra]<sz[rb]) swap(ra,rb);
sz[ra]+=sz[rb];
arr[rb]=ra;
}
}dsu;
vector<pii>edge;
void build_tree(){
shuffle(edge.begin(),edge.end(),rng);
dsu.init(n);
for (auto [u,v]:edge){
if (dsu.find(u)!=dsu.find(v)){
tre[u].push_back(v);
tre[v].push_back(u);
dsu.Merge(u,v);
}
}
}
void get_tree(int p){
vis[p]=1;
shuffle(g[p].begin(),g[p].end(),rng);
for (auto i:g[p]){
if (!vis[i]){
tre[i].push_back(p);
tre[p].push_back(i);
get_tree(i);
}
}
}
void count_size(int p,int lp){
sz[p]=1; deg[p]=tre[p].size(); mx[p]=0;
for (auto i:tre[p]){
if (i!=lp){
count_size(i,p);
mx[p]=max(mx[p],sz[i]);
sz[p]+=sz[i];
}
}
mx[p]=max(mx[p],(n-sz[p]));
}
void dfs1(int p,int lp){
res[p]=1;
if (tre[p].size()==1)
leaf1.push_back(p);
for (auto i:tre[p])
if (i!=lp)
dfs1(i,p);
}
void dfs2(int p,int lp){
res[p]=2;
if (tre[p].size()==1)
leaf2.push_back(p);
for (auto i:tre[p])
if (i!=lp)
dfs2(i,p);
}
void solve(){
count_size(1,0);
int mid=0;
for (int i=1;i<=n;i++){
if (mx[i]>=A&&n-mx[i]>=B){
mid=i;
break;
}
else if (mx[i]>=B&&n-mx[i]>=A){
mid=i;
break;
}
}
if (mid==0) return;
count_size(mid,0);
vector<pii>all;
for (auto i:tre[mid])
all.push_back({sz[i],i});
sort(all.begin(),all.end());
int now1=0,now2=0;
if (all.back().x>=B){
dfs2(all.back().y,mid);
now2=all.back().x;
for (int i=0;i<all.size()-1;i++){
dfs1(all[i].y,mid);
now1+=all[i].x;
}
res[mid]=1; now1++;
}
else {
dfs1(all.back().y,mid);
now1=all.back().x;
for (int i=0;i<all.size()-1;i++){
dfs2(all[i].y,mid);
now2+=all[i].x;
}
res[mid]=2; now2++;
}
while (now1>A){
int out=leaf1.back(); leaf1.pop_back();
res[out]=3; now1--;
for (auto i:tre[out]){
deg[i]--;
if (deg[i]==1)
leaf1.push_back(i);
}
}
while (now2>B){
int out=leaf2.back(); leaf2.pop_back();
res[out]=3; now2--;
for (auto i:tre[out]){
deg[i]--;
if (deg[i]==1)
leaf2.push_back(i);
}
}
}
void reset(){
fill(res.begin(),res.end(),0);
leaf1.clear(); leaf2.clear();
for (int j=1;j<=n;j++){
tre[j].clear(); vis[j]=0;
deg[j]=0; sz[j]=0;
}
}
vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
n=_n;
vector<pii>s={{a,1},{b,2},{c,3}};
sort(s.begin(),s.end());
A=s[0].x; B=s[1].x; C=s[2].x;
for (int i=0;i<p.size();i++){
edge.push_back({p[i]+1,q[i]+1});
g[p[i]+1].push_back(q[i]+1);
g[q[i]+1].push_back(p[i]+1);
}
res.resize(n+1);
for (int i=1;i<=n;i++){
reset();
//build_tree();
get_tree(i);
solve();
if (res[1]) break;
}
vector<int>ans; ans.resize(n,0);
if (res[1]==0) return ans;
for (int i=1;i<=n;i++)
ans[i-1]=(s[res[i]-1].y);
int sz[4]={};
for (auto i:ans)
sz[i]++;
assert(sz[1]==a&&sz[2]==b&&sz[3]==c);
return ans;
}
