#include "split.h"
#include<bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define all(x) x.begin(),x.end()
const int N=100005;
vector<int> adj[N],res;
int sz[N],pa[N];
pair<int,int> p={-1,-1};
int n;
int cnt=0;
void get_sz(int k){
sz[k]=1;
for(int j:adj[k]){
if(j==pa[k]){
continue;
}
pa[j]=k;
get_sz(j);
sz[k]+=sz[j];
//sort(all(adj[k]),[&](int a,int b){return sz[a]<sz[b];});
}
}
int cen(int k,int sz1){
for(int j:adj[k]){
if(j==pa[k]){
continue;
}
if(sz[j]*2>=sz1){
return cen(j,sz1);
}
}
return k;
}
void dfs(int k,int pa,int goal){
if(sz[k]>=goal){
p=max(p,{n-sz[k],k});
}
for(int j:adj[k]){
if(j==pa){
continue;
}
dfs(j,k,goal);
}
}
void draw(int k,int pa,bool yes,int root,int goal,int num){
if(k==root){
yes=1;
}
if(cnt==goal){
return;
}
if(yes){
cnt++;
res[k]=num;
}
for(int j:adj[k]){
if(j==pa){
continue;
}
draw(j,k,yes,root,goal,num);
}
}
vector<int> find_split(int n1, int a, int b, int c, vector<int> x, vector<int> y) {
vector<int> ans1={0,1,2,3};
if(a>b){
swap(a,b);
swap(ans1[1],ans1[2]);
}
if(a>c){
swap(a,c);
swap(ans1[1],ans1[3]);
}
if(b>c){
swap(b,c);
swap(ans1[2],ans1[3]);
}
/*if(a<b){
swap(a,b);
swap(ans1[1],ans1[2]);
}*/
ans1[0]=ans1[3];
n=n1;
res.resize(n);
int m=x.size();
for(int i=0;i<m;i++){
adj[x[i]].push_back(y[i]);
adj[y[i]].push_back(x[i]);
}
get_sz(0);
int c1=cen(0,n);
get_sz(c1);
pa[c1]=c1;
dfs(c1,c1,a);
if(p.first<b){
return res;
}
draw(c1,c1,0,p.second,a,1);
cnt=0;
draw(pa[p.second],p.second,0,pa[p.second],b,2);
for(int i=0;i<n;i++){
res[i]=ans1[res[i]];
}
return res;
}
/*
7 6 4 2 1
0 1
0 2
1 3
1 4
2 5
2 6
*/
/*
10 9 2 7 1
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
*/
