#include "split.h"
#include <iostream>
#include <vector>
using namespace std;
const int MAX_SOMMET = 1e5+42;
vector<int> adj[MAX_SOMMET];
int iEnsemble[3] = {1, 2, 3};
int tEnsemble[3];
int nbSommet, nbArete;
vector<int> arbre[MAX_SOMMET];
bool vu[MAX_SOMMET] = {0};
void calcArbre(int sommet) {
vu[sommet] = 1;
for(auto voisin : adj[sommet]) {
if(!vu[voisin]) {
arbre[sommet].push_back(voisin);
arbre[voisin].push_back(sommet);
calcArbre(voisin);
}
}
}
int tailleComp[MAX_SOMMET] = {0};
int calcTaille(int sommet, int pere) {
tailleComp[sommet] = 1;
for(auto voisin : arbre[sommet]) {
if(voisin == pere) continue;
tailleComp[sommet] += calcTaille(voisin, sommet);
}
return tailleComp[sommet];
}
int calcCentroid(int sommet, int pere) {
for(auto voisin : arbre[sommet]) {
if(voisin == pere) continue;
if(tailleComp[voisin] * 2 > nbSommet)
return calcCentroid(voisin, sommet);
}
return sommet;
}
int centroid;
int uf[MAX_SOMMET];
int tailleUf[MAX_SOMMET];
int trouver(int x) {
if(uf[x] == x)
return x;
return uf[x] = trouver(uf[x]);
}
void unir(int a, int b) {
int pa = trouver(a);
int pb = trouver(b);
if(pa != pb) {
uf[pb] = pa;
tailleUf[pa] += tailleUf[pb];
}
}
void initUf(int sommet, int pere) {
if(pere != centroid && sommet != centroid)
unir(pere, sommet);
for(auto voisin : arbre[sommet]) {
if(voisin == pere) continue;
initUf(voisin, sommet);
}
}
int idComp() {
for(int sommet = 0; sommet < nbSommet; sommet++) {
if(tailleUf[trouver(sommet)] >= tEnsemble[0] && sommet != centroid)
return trouver(sommet);
}
for(int sommet = 0; sommet < nbSommet; sommet++) {
for(auto voisin : adj[sommet]) {
if(sommet == centroid || voisin == centroid) continue;
unir(sommet, voisin);
if(tailleUf[trouver(sommet)] >= tEnsemble[0])
return trouver(sommet);
}
}
return -1;
}
int compA;
vector<int> rep;
bool vuA[MAX_SOMMET] = {0};
int nbRestantA;
void dfsA(int sommet) {
if(vuA[sommet] || trouver(sommet) != compA || nbRestantA == 0)
return;
vuA[sommet] = 1;
rep[sommet] = iEnsemble[0];
nbRestantA--;
for(auto voisin : adj[sommet])
dfsA(voisin);
}
bool vuB[MAX_SOMMET] = {0};
int nbRestantB;
void dfsB(int sommet) {
if(vuB[sommet] || nbRestantB == 0 || rep[sommet] != 0)
return;
vuB[sommet] = 1;
nbRestantB--;
rep[sommet] = iEnsemble[1];
for(auto voisin : adj[sommet])
dfsB(voisin);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
nbSommet = n, nbArete = p.size();
tEnsemble[0] = a, tEnsemble[1] = b, tEnsemble[2] = c;
for(int sommet = 0; sommet < nbSommet; sommet++) {
tailleUf[sommet] = 1;
uf[sommet] = sommet;
rep.push_back(0);
}
for(int id : {0, 1, 0}) {
if(tEnsemble[id] > tEnsemble[id+1]) {
swap(tEnsemble[id], tEnsemble[id+1]);
swap(iEnsemble[id], iEnsemble[id+1]);
}
}
for(int id = 0; id < nbArete; id++) {
adj[p[id]].push_back(q[id]);
adj[q[id]].push_back(p[id]);
}
calcArbre(0);
calcTaille(0, -1);
centroid = calcCentroid(0, -1);
initUf(centroid, -1);
compA = idComp();
if(compA == -1)
return rep;
nbRestantA = tEnsemble[0];
for(auto voisin : adj[centroid]) {
if(trouver(voisin) == compA) {
dfsA(voisin);
break;
}
}
nbRestantB = tEnsemble[1];
dfsB(centroid);
for(int sommet = 0; sommet < nbSommet; sommet++) {
if(rep[sommet] == 0)
rep[sommet] = iEnsemble[2];
}
return rep;
}
