#include "split.h"
#include <bits/stdc++.h>
#define PB push_back
#define distancia first
#define hacia second
using namespace std;
vector<int>ady[100001];
vector<int>stt, stt2;
int A, B, N, dist[100001], tama, tamb;
bool reco[100001];
int bfs1(int start){
int rta;
queue<pair<int, int> >quiu;
bool recorrido[100001];
quiu.push({0, start});
//memset(recorrido, false, sizeof recorrido);
for(int i = 0 ; i < N ; i++)recorrido[i]=false;
recorrido[start]=true;
while(quiu.size()){
int u = quiu.front().hacia, di=quiu.front().distancia;
for(auto i : ady[u]){
if(recorrido[i])continue;
quiu.push({di+1, i});
recorrido[i]=true;
rta=i;
}
quiu.pop();
}return rta;
}
int bfs2(int start){
int rta;
queue<pair<int, int> >quiu;
bool recorrido[100001];
//memset(recorrido, false, sizeof recorrido);
quiu.push({0, start});
dist[start]=0;
for(int i = 0 ; i < N ; i++)recorrido[i]=false;
recorrido[start]=true;
while(quiu.size()){
int u = quiu.front().hacia, di=quiu.front().distancia;
//cout<<u<<endl;
for(auto i : ady[u]){
if(recorrido[i])continue;
quiu.push({di+1, i});
dist[i]=di+1;
recorrido[i]=true;
rta=i;
}
quiu.pop();
}return rta;
}
int bfs3(int start){
int rta=0, cont=0;
priority_queue<pair<int, int> >quiu;
bool recorrido[100001];
//memset(recorrido, false, sizeof recorrido);
quiu.push({dist[start], start});
//dist[start]=0;
for(int i = 0 ; i < N ; i++)recorrido[i]=false;
recorrido[start]=true;
while(quiu.size()){
int u = quiu.top().hacia, di=quiu.top().distancia;
//cout<<u<<endl;
stt.PB(u);
reco[u]=true;
cont++;
if(cont==tamb){
return 1;
}
quiu.pop();
for(auto i : ady[u]){
if(recorrido[i])continue;
quiu.push({dist[i], i});
//dist[i]=di+1;
recorrido[i]=true;
rta=i;
}
}return rta;
}
int bfs4(int start){
int rta=-1, cont=0;
queue<pair<int, int> >quiu;
bool recorrido[100001];
//memset(recorrido, false, sizeof recorrido);
quiu.push({dist[start], start});
//dist[start]=0;
for(int i = 0 ; i < N ; i++)recorrido[i]=false;
recorrido[start]=true;
while(quiu.size()){
int u = quiu.front().hacia, di=quiu.front().distancia;
//cout<<u<<endl;
stt2.PB(u);
reco[u]=true;
cont++;
if(cont==tama){
return 1;
}
quiu.pop();
for(auto i : ady[u]){
if(recorrido[i]||reco[i])continue;
quiu.push({dist[i], i});
//dist[i]=di+1;
recorrido[i]=true;
//rta=i;
}
}return rta;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<int> res;
N=n;
for(int i = 0 ; i < p.size () ; i++){
ady[p[i]].PB(q[i]);
ady[q[i]].PB(p[i]);
}
if(a>c)swap(a, c);
if(b>c)swap(b, c);
if(a>b)swap(a, b);
tama=a, tamb=b;
A=bfs1(1);
//cout<<A<<endl;
B=bfs2(A);
//cout<<B<<endl;
bfs3(B);
//for(int i = 0 ; i < n ; i++)cout<<dist[i]<<" ";
res.resize(n);
if(bfs4(A)!=-1) {
for(int i = 0 ; i < n ; i++){
res[i]=3;
}
for(auto i:stt){
res[i]=1;
}
for(auto i:stt2){
res[i]=2;
}
} else {
for(int i = 0 ; i < n ; i++){
res[i]=0 ;
}
}
return res;
}
