#include <vector>
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int oo = 1e9 + 9;
const int MAX = 3e5 + 5;
struct edge{
int v, u, c;
};
int n, m;
vector<edge> g[MAX];
int K[MAX];
vector<int> ans;
vector<bool> done(MAX, 0);
int mnAns = oo;
bool visited[MAX], hasKey[MAX];
vector<int> blockedList[MAX];
vector<int> keys, v;
set<int> blocked;
void clear(){
for(int a:v){
visited[a] = 0;
}
for(int a:keys){
hasKey[a] = 0;
}
for(auto a:blocked){
vector<int> tmp;
swap(blockedList[a], tmp);
}
blocked.clear();
v.clear();
keys.clear();
set<int> tmp1;
swap(tmp1, blocked);
vector<int> tmp2, tmp3;
swap(tmp2, keys);
swap(tmp3, v);
}
int bfs(int start){
queue<int> q;
q.push(start);
v.push_back(start);
visited[start] = 1;
int cnt = 1;
while(q.size()){
int node = q.front();
int k = K[node];
q.pop();
if(!hasKey[k]){
blocked.erase(k);
hasKey[k] = 1;
keys.push_back(k);
for(int a:blockedList[k]){
if(visited[a]) continue;
cnt++;
if(done[a]){
return oo;
}
visited[a] = 1;
v.push_back(a);
q.push(a);
}
vector<int> tmp;
swap(blockedList[k], tmp);
}
for(auto e:g[node]){
if(visited[e.u]) continue;
if(hasKey[e.c]){
cnt++;
if(done[e.u]){
return oo;
}
visited[e.u] = 1;
v.push_back(e.u);
q.push(e.u);
}
else{
blocked.insert(e.c);
blockedList[e.c].push_back(e.u);
}
}
}
for(int a:v){
ans[a] = min(ans[a], cnt);
}
return cnt;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
n = r.size();
m = u.size();
for (int i = 0; i < n; i++)
{
K[i] = r[i];
}
for (int i = 0; i < m; i++)
{
g[u[i]].push_back({u[i], v[i], c[i]});
g[v[i]].push_back({v[i], u[i], c[i]});
}
ans.resize(n, oo);
vector<int> order(n);
iota(order.begin(), order.end(), 0);
random_shuffle(order.begin(), order.end());
for(int node:order){
mnAns = min(mnAns, bfs(node));
done[node] = 1;
clear();
}
vector<int> cnt(n, 0);
for (int i = 0; i < n; i++)
{
if(ans[i] == mnAns){
cnt[i] = 1;
}
}
return cnt;
}
