#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;
int mnAns = n;
bool visited[MAX], hasKey[MAX];
vector<int> blockedList[MAX];
vector<set<int>> st;
int reachable[MAX];
void bfs(int start){
vector<int> keys, v;
set<int> blocked;
queue<int> q;
q.push(start);
int cnt = 0;
while(q.size()){
int node = q.front();
int k = K[node];
q.pop();
if(visited[node]) continue;
//cout << node << '\n';
cnt += 1;
if(cnt > mnAns){
ans[start] = n + 1;
break;
}
if(ans[node] != -1){
if(ans[node] > mnAns){
ans[start] = n + 1;
break;
}
set<int>& s = st[reachable[node]];
if(s.count(start)){
ans[start] = ans[node];
reachable[start] = reachable[node];
break;
}
else{
ans[start] = n + 1;
break;
}
}
visited[node] = 1;
v.push_back(node);
if(!hasKey[k]){
blocked.erase(k);
hasKey[k] = 1;
keys.push_back(k);
for(int a:blockedList[k]){
q.push(a);
}
vector<int> tmp;
swap(blockedList[k], tmp);
}
for(auto e:g[node]){
if(hasKey[e.c]){
q.push(e.u);
}
else{
blocked.insert(e.c);
blockedList[e.c].push_back(e.u);
}
}
}
for(int b:blocked){
vector<int> tmp;
swap(tmp, blockedList[b]);
}
for(int k:keys){
hasKey[k] = 0;
}
for(int node:v){
visited[node] = 0;
}
if(ans[start] == -1){
ans[start] = cnt;
reachable[start] = st.size();
st.push_back(set<int>());
set<int>& tmp = st.back();
for(int a:v){
tmp.insert(a);
}
}
mnAns = min(mnAns, ans[start]);
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
n = r.size();
mnAns = n;
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]});
}
memset(reachable, -1, sizeof(reachable));
ans.resize(n, -1);
vector<int> order(n);
iota(order.begin(), order.end(), 0);
random_shuffle(order.begin(), order.end());
for(int node:order){
//cout << node << ":\n";
bfs(node);
}
vector<int> cnt(n, 0);
for (int i = 0; i < n; i++)
{
//cout << ans[i] << ' ';
if(ans[i] == mnAns){
cnt[i] = 1;
}
}
//cout << '\n';
return cnt;
}
