#include<bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
#pragma GCC optimize(3)
vector<pair<int,int>>adj[300100];
int col[300100],got[300100],went[300100],bst;
vector<int> onez;
bitset<300100>don;
VI unlocked[300100];
mt19937 rng(random_device{}());
int CDC;
void simul(int n){
CDC++;
queue<int>q;
q.push(n);
int CNT=0;
went[n]=CDC;
unordered_set<int>hav;
while(q.size()){
int x=q.front();
q.pop();
CNT++;
if(CNT>bst)break;
went[x]=CDC;
if(got[col[x]]^CDC){
got[col[x]]=CDC;
for(auto i:unlocked[col[x]])
if(went[i]^CDC) {
q.push(i),went[i]=CDC;
if(don[i]){CNT=1e9;goto hmm;}
}
unlocked[col[x]].clear();
}
for(auto[v,c]:adj[x])
if(got[c]==CDC) {
if(went[v]^CDC) {
q.push(v),went[v]=CDC;
if(don[v]){CNT=1e9;goto hmm;}
}
}else unlocked[c].push_back(v),hav.insert(c);
}
hmm:
don[n]=1;
for(auto i:hav)
unlocked[i].clear();
if(CNT<bst)
bst=CNT,onez.clear();
if(CNT==bst)
onez.push_back(n);
}
VI find_reachable(VI r, VI u, VI v, VI c) {
bst=1e9;
int n=r.size(),m=c.size();
VI ord(n),ans(n);
iota(ord.begin(),ord.end(),0);
shuffle(ord.begin(),ord.end(),rng);
for(int i=0;i<n;i++)
col[i]=r[i];
for(int i=0;i<m;i++)
adj[u[i]].push_back({v[i],c[i]}),
adj[v[i]].push_back({u[i],c[i]});
for(int i=0;i<n;i++)
shuffle(adj[i].begin(),adj[i].end(),rng);
for(auto i:ord)
simul(i);
don.reset();
int x=onez.size();
for(int i=0;i<x;i++)
simul(onez[i]);
for(int i=0;i<n;i++)
if(went[i]>n)
ans[i]=1;
return ans;
}
