#include <bits/stdc++.h>
using namespace std;
struct Component
{
vector<int> nodes;
set<int> owned;
map<int,vector<int>> pending;
queue<int> ready;
};
int parent[300005];
Component comps[300005];
int find(int i)
{
int root=i;
while(parent[root]!=root)
{
root=parent[root];
}
while(parent[i]!=root)
{
int next=parent[i];
parent[i]=root;
i=next;
}
return root;
}
int merge(int u, int v)
{
u=find(u);
v=find(v);
if(u==v)
{
return u;
}
if(comps[u].nodes.size()<comps[v].nodes.size())
{
swap(u,v);
}
parent[v]=u;
for(int node : comps[v].nodes)
{
comps[u].nodes.push_back(node);
}
comps[v].nodes.clear();
for(int k : comps[v].owned)
{
if(comps[u].owned.find(k)==comps[u].owned.end())
{
comps[u].owned.insert(k);
auto it=comps[u].pending.find(k);
if(it != comps[u].pending.end())
{
for(int target : it->second)
{
comps[u].ready.push(target);
}
comps[u].pending.erase(it);
}
}
}
comps[v].owned.clear();
for(auto& entry : comps[v].pending)
{
int k=entry.first;
if(comps[u].owned.count(k))
{
for(int target : entry.second)
{
comps[u].ready.push(target);
}
}
else
{
vector<int>& vec=comps[u].pending[k];
if(vec.size()<entry.second.size())
{
swap(vec,entry.second);
}
vec.insert(vec.end(),entry.second.begin(),entry.second.end());
}
}
comps[v].pending.clear();
while(!comps[v].ready.empty())
{
comps[u].ready.push(comps[v].ready.front());
comps[v].ready.pop();
}
return u;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
int n=r.size();
int m=u.size();
vector<vector<pair<int,int>>> adj(n);
for(int i=0; i<m; 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++)
{
parent[i]=i;
comps[i].nodes={i};
comps[i].owned={r[i]};
comps[i].pending.clear();
while(!comps[i].ready.empty())
{
comps[i].ready.pop();
}
for(auto& edge : adj[i])
{
if(edge.first==r[i])
{
comps[i].ready.push(edge.second);
}
else
{
comps[i].pending[edge.first].push_back(edge.second);
}
}
}
vector<bool> used(n,false);
vector<bool> active(n,false);
vector<int> sink;
for(int i=0; i<n; i++)
{
int root=find(i);
if(used[root])
{
continue;
}
vector<int> path;
used[root]=true;
active[root]=true;
path.push_back(root);
while(!path.empty())
{
int p=path.back();
int next=-1;
while(!comps[p].ready.empty())
{
int target=comps[p].ready.front();
comps[p].ready.pop();
int tr=find(target);
if(tr!=p)
{
next=tr;
break;
}
}
if(next!=-1)
{
if(active[next])
{
while(path.back()!=next)
{
int w=path.back();
path.pop_back();
active[w]=false;
next=merge(next,w);
}
path.pop_back();
path.push_back(next);
active[next]=true;
}
else if(used[next])
{
for(int w : path)
{
active[w]=false;
}
path.clear();
}
else
{
used[next]=true;
active[next]=true;
path.push_back(next);
}
}
else
{
sink.push_back(p);
for(int w : path)
{
active[w]=false;
}
path.clear();
}
}
}
int reachable=n+1;
for(int root : sink)
{
reachable=min(reachable,(int)comps[root].nodes.size());
}
vector<int> ans(n,0);
for(int root : sink)
{
if((int)comps[root].nodes.size()==reachable)
{
for(int node : comps[root].nodes)
{
ans[node]=1;
}
}
}
return ans;
}
