#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, tamc;
bool reco[100001];
int bfs1(int start){
int rta=0;
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=0;
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;
if(dist[i]>dist[rta])rta=i;
//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==tama){
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==tamb){
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]);
}
tama=a, tamb=b, tamc=c;
if(tama>tamc)swap(tama, tamc);
if(tamb>tamc)swap(tamb, tamc);
if(tama>tamb)swap(tama, tamb);
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(B)!=-1) {
int temp=(n-stt.size());
temp-=stt2.size();
if(temp==c)temp=3;
else if(temp==b)temp=2;
else temp=1;
for(int i = 0 ; i < n ; i++){
res.PB(temp);
}
int temp2;
temp2=stt.size();
if(temp2==c&&temp!=3)temp2=3;
else if(temp2==b&&temp!=2)temp2=2;
else temp2=1;
//temp=1;
for(auto i:stt){
res[i]=temp2;
}
int temp3=stt2.size();
if(temp3==c&&temp!=3&&temp2!=3)temp3=3;
else if(temp3==b&&temp!=2&&temp2!=2)temp3=2;
else temp3=1;
for(auto i:stt2){
res[i]=temp3;
}
} else {
for(int i = 0 ; i < n ; i++){
res.PB(0);
}
}
return res;
}
