#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define fir first
#define sec second
const int mxN=300100;
int N, M;
queue <int> que;
queue <int> cque[mxN];
vector <pii> adj[mxN];
vector <int> ans;
bool Chk[mxN], CChk[mxN];
int cnt=1000000;
void unlock(int cnum)
{
CChk[cnum]=true;
while(!cque[cnum].empty())
{
int now=cque[cnum].front();
cque[cnum].pop();
if(Chk[now]) continue;
Chk[now]=true;
que.push(now);
}
}
void push_in(int nnum, int cnum)
{
if(CChk[cnum])
{
if(Chk[nnum]) return;
Chk[nnum]=true;
que.push(nnum);
}
else
{
cque[cnum].push(nnum);
}
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
N=r.size();
M=u.size();
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]});
}
ans.resize(N);
for(int i=0;i<N;i++)
{
while(!que.empty()) que.pop();
for(int j=0;j<N;j++) while(!cque[j].empty()) cque[j].pop();
for(int j=0;j<N;j++) Chk[j]=false, CChk[j]=false;
que.push(i);
Chk[i]=true;
while(!que.empty())
{
int now=que.front();
que.pop();
if(!CChk[r[now]])
{
unlock(r[now]);
}
for(pii nxt : adj[now])
{
if(!Chk[nxt.fir]) push_in(nxt.fir, nxt.sec);
}
}
for(int j=0;j<N;j++) if(Chk[j]) ans[i]++;
}
for(int i=0;i<N;i++) cnt=min(cnt, ans[i]);
for(int i=0;i<N;i++) ans[i]=(ans[i]==cnt ? 1 : 0);
return ans;
}
