#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],leaf1,leaf2,res;
vector<pii>change;
set<int>tre[N];
int sz[N],a,b,c,mx[N],deg[N],fa[N],cnt[N],n,dfn[N],t=0,now1,now2;
void get_tree(int p,int lp){
fa[p]=lp; dfn[p]=++t;
for (auto i:g[p]){
if (!dfn[i]){
tre[i].insert(p);
tre[p].insert(i);
get_tree(i,p);
cnt[p]+=cnt[i];
}
else if (i!=lp&&dfn[i]<dfn[p]){
cnt[p]++; cnt[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];
}
}
}
void dfs1(int p,int lp){
res[p]=1; now1++;
if (tre[p].size()==1)
leaf1.push_back(p);
for (auto i:tre[p])
if (i!=lp&&!res[i])
dfs1(i,p);
}
void dfs2(int p,int lp){
res[p]=2; now2++;
if (tre[p].size()==1)
leaf2.push_back(p);
for (auto i:tre[p])
if (i!=lp&&!res[i])
dfs2(i,p);
}
bool check(int i){
if (sz[i]>=a&&sz[i]<=n-a)
return 1;
vector<pii>all;
for (auto j:tre[i]){
if (j!=fa[i]&&cnt[j])
all.push_back({sz[j],j});
}
sort(all.begin(),all.end());
change.clear();
int now=sz[i];
for (auto [s,j]:all){
now-=s;
change.push_back({i,j});
if (now>=a&&now<=n-a){
for (auto [a,b]:change){
tre[a].erase(b);
tre[b].erase(a);
}
sz[i]=now;
return 1;
}
}
return 0;
}
void solve(){
count_size(1,0);
int mid=0;
for (int i=1;i<=n;i++){
if (check(i)){
mid=i;
break;
}
}
if (mid==0) return;
if (sz[mid]>=b){
dfs2(mid,fa[mid]);
for (auto [a,b]:change){
tre[a].insert(b);
tre[b].insert(a);
}
dfs1(mid,mid);
}
else {
dfs1(mid,fa[mid]);
for (auto [a,b]:change){
tre[a].insert(b);
tre[b].insert(a);
}
dfs2(mid,mid);
}
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);
}
}
}
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++){
g[p[i]+1].push_back(q[i]+1);
g[q[i]+1].push_back(p[i]+1);
}
res.resize(n+1);
get_tree(1,0); solve();
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);
return ans;
}
/*
10 10
4 3 3
0 1
1 2
1 4
1 5
4 6
0 7
3 8
2 9
0 3
1 3
*/
