#include <bits/stdc++.h>
using namespace std;
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({v[i],c[i]});
adj[v[i]].push_back({u[i],c[i]});
}
vector<int> parent(n);
iota(parent.begin(),parent.end(),0);
auto find=[&](auto self, int i) -> int
{
return(parent[i]==i) ? i :(parent[i]=self(self,parent[i]));
};
vector<set<int>> visited(n);
vector<set<int>> held(n);
vector<map<int,vector<int>>> blocked(n);
vector<queue<int>> q(n);
vector<int> status(n,0);
vector<bool> dead(n,false);
for(int i=0; i<n; i++)
{
visited[i].insert(i);
q[i].push(i);
}
auto merge=[&](int a, int b)
{
a=find(find,a);
b=find(find,b);
if(a==b)
{
return a;
}
if(visited[a].size()<visited[b].size())
{
swap(a,b);
}
parent[b]=a;
for(int k : held[b])
{
if(held[a].find(k)==held[a].end())
{
held[a].insert(k);
if(blocked[a].count(k))
{
for(int target : blocked[a][k])
{
if(visited[a].find(target)==visited[a].end())
{
visited[a].insert(target);
q[a].push(target);
}
}
blocked[a].erase(k);
}
}
}
for(auto& it : blocked[b])
{
int k=it.first;
if(held[a].count(k))
{
for(int target : it.second)
{
if(visited[a].find(target)==visited[a].end())
{
visited[a].insert(target);
q[a].push(target);
}
}
}
else
{
vector<int>& vec=blocked[a][k];
vec.insert(vec.end(),it.second.begin(),it.second.end());
}
}
while(!q[b].empty())
{
q[a].push(q[b].front());
q[b].pop();
}
for(int room : visited[b])
{
visited[a].insert(room);
}
held[b].clear();
blocked[b].clear();
visited[b].clear();
return a;
};
vector<int> final;
for(int i=0; i<n; i++)
{
int root=find(find,i);
if(status[root]!=0)
{
continue;
}
vector<int> path;
path.push_back(root);
status[root]=1;
while(!path.empty())
{
int curr=path.back();
int next=-1;
while(!q[curr].empty())
{
int idx=q[curr].front();
int target=find(find,idx);
if(target!=curr)
{
next=target;
break;
}
q[curr].pop();
int type=r[idx];
if(held[curr].find(type)==held[curr].end())
{
held[curr].insert(type);
if(blocked[curr].count(type))
{
for(int neighbor : blocked[curr][type])
{
if(visited[curr].find(neighbor)==visited[curr].end())
{
visited[curr].insert(neighbor);
q[curr].push(neighbor);
}
}
blocked[curr].erase(type);
}
}
for(auto& edge : adj[idx])
{
if(held[curr].count(edge.second))
{
if(visited[curr].find(edge.first)==visited[curr].end())
{
visited[curr].insert(edge.first);
q[curr].push(edge.first);
}
}
else
{
blocked[curr][edge.second].push_back(edge.first);
}
}
}
if(next==-1)
{
status[curr]=2;
final.push_back(curr);
path.pop_back();
}
else if(status[next]==1)
{
int merged=curr;
while(path.back()!=next)
{
path.pop_back();
merged=merge(merged,path.back());
}
path.pop_back();
path.push_back(merged);
}
else if(status[next]==2)
{
for(int node : path)
{
status[node]=2;
dead[node]=true;
}
path.clear();
}
else
{
status[next]=1;
path.push_back(next);
}
}
}
int np=n+1;
for(int sink : final)
{
if(!dead[sink])
{
np=min(np,(int)visited[sink].size());
}
}
vector<int> ans(n,0);
for(int sink : final)
{
if(!dead[sink] &&(int)visited[sink].size()==np)
{
for(int room : visited[sink])
{
ans[room]=1;
}
}
}
return ans;
}
