#include <bits/stdc++.h>
using namespace std;
const int MAX_N=300005;
const int INF=1e9+7;
set<pair<int,int>> wait[MAX_N];
vector<int> todo[MAX_N];
set<int> has[MAX_N];
int sz[MAX_N];
int id[MAX_N];
int vis[MAX_N];
int timer=0;
vector<int> nodes[MAX_N];
void merge(int u, int v)
{
u=id[u];
v=id[v];
if(u==v)
{
return;
}
if(sz[u]>sz[v])
{
swap(u,v);
}
sz[v]+=sz[u];
for(int x : nodes[u])
{
nodes[v].push_back(x);
id[x]=v;
}
nodes[u].clear();
for(int x : todo[u])
{
todo[v].push_back(x);
}
todo[u].clear();
for(auto &e : wait[u])
{
if(has[v].count(e.first))
{
todo[v].push_back(e.second);
}
else
{
wait[v].insert(e);
}
}
wait[u].clear();
for(int k : has[u])
{
auto it=wait[v].lower_bound({k,-1});
while(it!=wait[v].end() && it->first==k)
{
todo[v].push_back(it->second);
wait[v].erase(it++);
}
has[v].insert(k);
}
has[u].clear();
}
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++)
{
has[i]={r[i]};
sz[i]=1;
id[i]=i;
nodes[i]={i};
todo[i].clear();
wait[i].clear();
vis[i]=0;
}
for(int i=0; i<m; i++)
{
if(has[u[i]].count(c[i]))
{
todo[u[i]].push_back(v[i]);
}
else
{
wait[u[i]].insert({c[i],v[i]});
}
if(has[v[i]].count(c[i]))
{
todo[v[i]].push_back(u[i]);
}
else
{
wait[v[i]].insert({c[i],u[i]});
}
}
int np=INF;
vector<int> best;
for(int i=0; i<n; i++)
{
if(vis[id[i]])
{
continue;
}
timer++;
int curr=id[i];
vector<int> stack;
while(true)
{
vis[curr]=timer;
if(todo[curr].empty())
{
if(sz[curr]<np)
{
np=sz[curr];
best=nodes[curr];
}
else if(sz[curr]==np)
{
for(int x : nodes[curr])
{
best.push_back(x);
}
}
break;
}
int target=todo[curr].back();
todo[curr].pop_back();
int next=id[target];
if(curr==next)
{
continue;
}
if(!vis[next])
{
stack.push_back(curr);
curr=next;
}
else if(vis[next]==timer)
{
while(true)
{
int p=stack.back();
stack.pop_back();
merge(curr,p);
if(p==next)
{
break;
}
}
curr=id[curr];
vis[curr]=timer;
}
else
{
break;
}
}
}
vector<int> res(n,0);
for(int x : best)
{
res[x]=1;
}
return res;
}
