#include <bits/stdc++.h>
using namespace std;
const int MAX_N=300005;
struct DSU
{
vector<int> p;
DSU(int n) : p(n)
{
iota(p.begin(),p.end(),0);
}
int find(int i)
{
return p[i]==i ? i : p[i]=find(p[i]);
}
void unite(int i, int j)
{
int root_i=find(i);
int root_j=find(j);
if(root_i!=root_j)
{
p[root_i]=root_j;
}
}
};
vector<pair<int,int>> adj[MAX_N];
int type[MAX_N];
int status[MAX_N];
int vis[MAX_N];
int has[MAX_N];
int timestamp;
vector<int> waiting[MAX_N];
int res[MAX_N];
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
int n=r.size();
int m=u.size();
for(int i=0; i<n; i++)
{
type[i]=r[i];
adj[i].clear();
status[i]=0;
vis[i]=0;
has[i]=0;
res[i]=n+1;
waiting[i].clear();
}
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]});
}
DSU dsu(n);
timestamp=0;
for(int i=0; i<n; i++)
{
while(status[dsu.find(i)]==0)
{
vector<int> stack;
int curr=dsu.find(i);
while(true)
{
status[curr]=1;
stack.push_back(curr);
timestamp++;
vector<int> q;
q.push_back(curr);
vis[curr]=timestamp;
int head=0;
int next=-1;
vector<int> ukeys,uwait;
while(head<(int)q.size())
{
int x=q[head++];
int k=type[x];
if(has[k]!=timestamp)
{
has[k]=timestamp;
ukeys.push_back(k);
for(int w : waiting[k])
{
if(vis[w]!=timestamp)
{
int root=dsu.find(w);
if(root!=curr)
{
next=root;
goto bfs;
}
vis[w]=timestamp;
q.push_back(w);
}
}
waiting[k].clear();
}
for(auto& edge : adj[x])
{
int y=edge.first;
int needed=edge.second;
if(has[needed]==timestamp)
{
if(vis[y]!=timestamp)
{
int root=dsu.find(y);
if(root!=curr)
{
next=root;
goto bfs;
}
vis[y]=timestamp;
q.push_back(y);
}
}
else
{
waiting[needed].push_back(y);
uwait.push_back(needed);
}
}
}
bfs:
for(int kw : uwait)
{
waiting[kw].clear();
}
if(next==-1)
{
res[curr]=q.size();
status[curr]=2;
stack.pop_back();
for(int node : stack)
{
status[node]=2;
}
break;
}
else
{
next=dsu.find(next);
if(status[next]==1)
{
while(stack.back()!=next)
{
int top=stack.back();
stack.pop_back();
dsu.unite(top,next);
}
curr=dsu.find(next);
stack.pop_back();
status[curr]=0;
break;
}
else if(status[next]==2)
{
for(int node : stack)
{
status[node]=2;
}
break;
}
else
{
curr=next;
}
}
}
}
}
int np=n+1;
for(int i=0; i<n; i++)
{
int root=dsu.find(i);
if(status[root]==2 && res[root]<=n)
{
np=min(np, res[root]);
}
}
vector<int> ans(n,0);
for(int i=0; i<n; i++)
{
int root=dsu.find(i);
if(res[root]==np)
{
ans[i]=1;
}
}
return ans;
}
