#pragma GCC optimize("O3")
#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];
int ans[MAX];
vector<bool> done(MAX, 0);
int mnAns = oo;
bool visited[MAX], hasKey[MAX];
vector<int> blockedList[MAX];
vector<int> keys, v, 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();
vector<int> tmp1, tmp2, tmp3;
swap(tmp1, blocked);
swap(tmp2, keys);
swap(tmp3, v);
}
queue<int> q;
int cnt = 1;
bool add(int a){
cnt++;
q.push(a);
visited[a] = 1;
v.push_back(a);
return cnt <= mnAns;
}
int bfs(int start){
queue<int> tmp;
swap(tmp, q);
cnt = 0;
add(start);
while(q.size()){
int node = q.front();
int k = K[node];
q.pop();
if(!hasKey[k]){
hasKey[k] = 1;
keys.push_back(k);
for(int a:blockedList[k]){
if(visited[a]) continue;
if(done[a] || !add(a)) return oo;
}
}
for(auto& e:g[node]){
if(visited[e.u]) continue;
if(hasKey[e.c]){
if(done[e.u] || !add(e.u)) return oo;
}
else{
blocked.push_back(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]});
}
fill(ans, ans + MAX, oo);
vector<int> order(n);
iota(order.begin(), order.end(), 0);
random_shuffle(order.begin(), order.end());
random_shuffle(order.begin(), order.end());
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;
}
