#include<bits/stdc++.h>
using namespace std;
const int TAILLE_MAX=300*1000+5;
int nbSom,nbAre,nbCompo;
int clef[TAILLE_MAX];
int taille[TAILLE_MAX];
set<int> listeDispo[TAILLE_MAX];
vector<pair<int,int>> adjaInit[TAILLE_MAX];
int pere[TAILLE_MAX];
vector<int> somInter,ordre;
int numCompo[TAILLE_MAX];
int dv[TAILLE_MAX];
vector<int> adja[TAILLE_MAX],adjaTrans[TAILLE_MAX];
vector<int> listeCompo[TAILLE_MAX];
int atteign[TAILLE_MAX];
int find(int pos) {
if (pos!=pere[pos]) {
pere[pos]=find(pere[pos]);
}
return pere[pos];
}
void DFS1(int pos) {
if (dv[pos]==0) {
dv[pos]=1;
for (int i:adja[pos]) {
DFS1(i);
}
ordre.push_back(pos);
}
}
void DFS2(int pos) {
if (numCompo[pos]==0) {
numCompo[pos]=nbCompo;
listeCompo[nbCompo].push_back(pos);
for (int i:adjaTrans[pos]) {
DFS2(i);
}
}
}
int dyna(int pos) {
if (atteign[pos]!=0) {
return atteign[pos];
}
atteign[pos]=taille[pos];
set<int> listeAtteign;
for (int i:adja[pos]) {
listeAtteign.insert(find(i));
}
for (int i:listeAtteign) {
atteign[pos]+=dyna(i);
}
return atteign[pos];
}
void calcAdja() {
somInter.clear();
for (int i=0;i<nbSom;i++) {
adja[i].clear();
adjaTrans[i].clear();
if (find(i)==i) {
somInter.push_back(i);
numCompo[i]=0;
dv[i]=0;
atteign[i]=0;
}
}
for (int i=0;i<nbSom;i++) {
for (auto j:adjaInit[i]) {
if ((*listeDispo[find(i)].lower_bound(j.second))==j.second and find(i)!=find(j.first)) {
//cout<<find(i)<<" "<<find(j.first)<<endl;
adja[find(i)].push_back(find(j.first));
adjaTrans[find(j.first)].push_back(find(i));
}
}
}
}
vector<int> find_reachable(vector<int> r,vector<int> u,vector<int> v,vector<int> c) {
nbSom=r.size();
nbAre=c.size();
for (int i=0;i<nbSom;i++) {
clef[i]=r[i];
pere[i]=i;
taille[i]=1;
listeDispo[i].insert(clef[i]);
}
for (int i=0;i<nbAre;i++) {
adjaInit[u[i]].push_back({v[i],c[i]});
adjaInit[v[i]].push_back({u[i],c[i]});
}
int modif=1,posMax=0,valMax,plusPetit;
while (modif==1) {
/*cout<<"NOUVEAU"<<endl;
for (int i=0;i<nbSom;i++) {
cout<<find(i)<<" ";
}
cout<<endl;*/
calcAdja();
ordre.clear();
for (int i:somInter) {
DFS1(i);
}
reverse(ordre.begin(),ordre.end());
nbCompo=0;
for (int i:ordre) {
if (numCompo[i]==0) {
nbCompo++;
listeCompo[nbCompo].clear();
DFS2(i);
}
}
modif=0;
somInter.clear();
for (int i=1;i<=nbCompo;i++) {
/*cout<<i<<" : ";
for (int j:listeCompo[i]) {
cout<<j<<" ";
}
cout<<endl;*/
if ((int)listeCompo[i].size()>1) {
modif=1;
valMax=0;
for (int j:listeCompo[i]) {
if (taille[j]>valMax) {
valMax=taille[j];
posMax=j;
}
}
somInter.push_back(posMax);
for (int j:listeCompo[i]) {
if (j!=posMax) {
taille[posMax]+=taille[j];
pere[j]=posMax;
for (int k:listeDispo[j]) {
listeDispo[posMax].insert(k);
}
for (int k:adja[j]) {
adja[posMax].push_back(k);
}
}
}
}
else {
somInter.push_back(listeCompo[i][0]);
}
}
plusPetit=TAILLE_MAX;
for (int i:somInter) {
atteign[i]=dyna(i);
plusPetit=min(plusPetit,atteign[i]);
}
if (modif==1) {
modif=0;
for (int i:somInter) {
if (taille[i]<plusPetit) {
modif=1;
}
}
}
}
vector<int> rep;
for (int i=0;i<nbSom;i++) {
atteign[i]=atteign[find(i)];
if (atteign[i]==plusPetit) {
rep.push_back(1);
}
else {
rep.push_back(0);
}
}
return rep;
}
