#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, cnt;
bool reco[100001], reco2[100001];
int bfs1(int start){//hallar nodo A
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){// hallar nodo B con respecto a A
int rta=0;
queue<pair<int, int> >quiu;
bool recorrido[100001];
//memset(recorrido, false, sizeof recorrido);
quiu.push({0, start});
dist[start]=0;
long long cont = 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;
if(cont==tamb){
return 1;
}else{
stt2.PB(u);
reco[u]=true;
reco2[u]=true;
cont++;
for(auto i : ady[u]){
if(recorrido[i])continue;
quiu.push({0, i});
dist[i]=0;
recorrido[i]=true;
//rta=i;
}
}
quiu.pop();
}return rta;
}
bool dfs(int node){
for(auto i:ady[node]){
if(reco2[i]||reco[i])continue;
cnt++;
reco2[i]=true;
dfs(i);
}
if(cnt>=tama){
if(stt.size()<tama){
reco[node]=true;
stt.PB(node);
}
return true;
}else return false;
}
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);//hallar nodo A
//cout<<A<<endl;
B=bfs2(A); // hallar nodo B con respecto a A
//cout<<B<<endl;
bool sepudo=false;
for(int i = 0 ; i < n ; i++){
if(!reco2[i]){
cnt=0;
if(dfs(i)){
sepudo=true;
break;
}
}
}
//bfs3(B); // hallar conjunto desde B con distancias de A
//for(int i = 0 ; i < n ; i++)cout<<dist[i]<<" ";
//res.resize(n);
if(sepudo) {
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;
}
