//////////////////////////////////////////////////////
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef vector<int> vi;
const int N=3e5+1;
int n,m;
vector<pair<int,int> >adj[N];
vi alive;
bool vis[N];
bool dead[N];
int gp[N];//group of i-th dude
vector<int>oid;//out = group
int ptr=0;
//in = groups
int l[N];
int mn[N];
vector<int>rdy[N];
vector<int>mem[N];
set<pair<int,pair<int,int> > >outs2;//in = late[color] out = edge
int late[N];//late[color]=last
void upd(int sid,int id,int rid){
for(auto c:adj[id]){
outs2.insert({late[c.fi],{id,c.se}});
}
int cur=rid;
while(true){
auto it=outs2.lower_bound({late[cur],{0,0}});
if(it==outs2.end() || it->fi!=late[cur]) break;
rdy[gp[it->se.fi]].push_back(it->se.se);
outs2.erase(it);
}
late[cur]=alive.size();
}
int merge(int p1,int p2){
if(rdy[p1].size()+mem[p1].size()<rdy[p2].size()+mem[p2].size()){
swap(p1,p2);
}
for(auto c:mem[p2]){
mem[p1].push_back(c);
gp[c]=p1;
}
for(auto c:rdy[p2]){
rdy[p1].push_back(c);
}
mem[p2].clear();rdy[p2].clear();
return p1;
}
int ans[N];
vi find_reachable(vi r,vi u,vi v,vi c){
n=r.size();
for(int i=0; i<u.size() ;i++){
adj[u[i]].push_back({c[i],v[i]});
adj[v[i]].push_back({c[i],u[i]});
}
for(int i=0; i<n ;i++) late[i]=-1-i;
for(int i=0; i<n ;i++){
if(!vis[i]){
vis[i]=true;
gp[i]=++ptr;
mem[gp[i]].push_back(i);
l[ptr]=0;
mn[ptr]=alive.size();
oid.push_back(ptr);
upd(ptr,i,r[i]);
alive.push_back(i);
while(true){
int cur=oid.back(),ly=oid.size();
/*cout << "List " << endl;
for(auto c:oid){
cout << "gp " << c << ": " << l[c] << endl;;
cout << "mem: ";
for(auto d:mem[c]){
cout << d << ' ';
}
cout << endl;
cout << "rdy: ";
for(auto d:rdy[c]){
cout << d << ' ';
}
cout << endl;
}*/
if(rdy[cur].empty()){//cycle end
int cnt=0;
for(auto c:alive){
if(l[gp[c]]==ly-1) ++cnt;
else ans[c]=n+1;
dead[c]=true;
late[r[c]]=-1-r[c];
}
for(auto c:alive) if(l[gp[c]]==ly-1) ans[c]=cnt;
alive.clear();oid.clear();outs2.clear();break;
}
int x=rdy[cur].back();rdy[cur].pop_back();
if(dead[x]){
for(auto c:alive){
dead[c]=true;
late[r[c]]=-1-r[c];
ans[c]=n+1;
}
alive.clear();oid.clear();outs2.clear();break;
}
else if(!vis[x]){
vis[x]=true;
gp[x]=++ptr;
mem[gp[x]].push_back(x);
l[ptr]=ly;
mn[ptr]=alive.size();
oid.push_back(ptr);
upd(ptr,x,r[x]);
alive.push_back(x);
}
else{//collapse layers
while(ly!=l[gp[x]]+1){
ly--;
int bad=mn[oid[ly-1]];
while(true){
auto it=outs2.lower_bound({bad,{0,0}});
if(it==outs2.end()) break;
rdy[gp[it->se.fi]].push_back(it->se.se);
outs2.erase(it);
}
mn[oid[ly-1]]=min(mn[oid[ly-1]],mn[oid[ly]]);
mn[oid[ly]]=min(mn[oid[ly-1]],mn[oid[ly]]);
oid[ly-1]=merge(oid[ly-1],oid[ly]);
l[oid[ly-1]]=ly-1;
oid.pop_back();
}
}
}
}
}
int mn=n;
for(int i=0; i<n ;i++) mn=min(mn,ans[i]);
vector<int>res(n);
for(int i=0; i<n ;i++) res[i]=(ans[i]==mn);
return res;
}
/////////////////////////////////////////////////////
