#include<bits/stdc++.h>
#include "split.h"
using namespace std;
const int MAX_SOM=100*1000+5;
int nbSom,nbAre,somPere,autreCompo,trouve,reste;
vector<int> rep;
vector<pair<int,int>> obj;
vector<int> adja[MAX_SOM];
int dv[MAX_SOM];
int prof[MAX_SOM];
int interdit[MAX_SOM];
int DFS(int pos) {
if (prof[pos]==0) {
prof[pos]=1;
for (int i:adja[pos]) {
prof[pos]+=DFS(i);
}
//cout<<pos<<" "<<prof[pos]<<endl;
return prof[pos];
}
return 0;
}
int calcDeb(int pos) {
for (int i:adja[pos]) {
if (prof[i]<prof[pos] and prof[i]>=obj[0].first) {
return calcDeb(i);
}
}
return pos;
}
void trouveMonte(int pos) {
if (dv[pos]==0) {
dv[pos]=1;
for (int i:adja[pos]) {
if (prof[i]>prof[somPere]) {
trouve=1;
}
else if (prof[i]<prof[pos]) {
trouveMonte(i);
}
}
}
}
void prop1(int pos) {
if (reste>0 and interdit[pos]==0 and rep[pos]==0) {
rep[pos]=obj[0].second;
reste--;
for (int i:adja[pos]) {
if (prof[i]<prof[pos]) {
prop1(i);
}
}
}
}
void prop2(int pos) {
if (reste>0 and rep[pos]==0) {
rep[pos]=obj[1].second;
reste--;
for (int i:adja[pos]) {
prop2(i);
}
}
}
vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q) {
nbSom=n;
nbAre=p.size();
obj={{a,1},{b,2},{c,3}};
sort(obj.begin(),obj.end());
rep.resize(nbSom);
for (int i=0;i<nbAre;i++) {
adja[p[i]].push_back(q[i]);
adja[q[i]].push_back(p[i]);
}
somPere=DFS(0);
somPere=calcDeb(0);
autreCompo=nbSom-prof[somPere];
//cout<<somPere<<endl;
for (int i:adja[somPere]) {
if (prof[i]<prof[somPere] and autreCompo<obj[0].first) {
trouve=0;
trouveMonte(i);
if (trouve==1) {
//cout<<i<<" ";
interdit[i]=1;
autreCompo+=prof[i];
}
}
}
//cout<<endl;
if (autreCompo<obj[0].first) {
return rep;
}
if (autreCompo<obj[1].first) {
swap(obj[0],obj[1]);
}
reste=obj[0].first;
prop1(somPere);
reste=obj[1].first;
prop2(0);
for (int i=0;i<nbSom;i++) {
if (rep[i]==0) {
rep[i]=obj[2].second;
}
}
return rep;
}
