#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> v, blocked;
void clear(){
for(int a:v){
visited[a] = 0;
hasKey[K[a]] = 0;
}
for(auto a:blocked){
blockedList[a].clear();
//vector<int> tmp;
//swap(blockedList[a], tmp);
}
blocked.clear();
v.clear();
//vector<int> tmp1, tmp2;
//swap(tmp1, blocked);
//swap(tmp2, 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;
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]});
}
for (int i = 0; i < n; i++)
{
random_shuffle(g[i].begin(), g[i].end());
}
fill(ans, ans + MAX, oo);
vector<int> p(2 * m);
for (int i = 0; i < m; i++)
{
p[2 * i] = u[i];
p[2 * i + 1] = v[i];
}
srand(time(0));
random_shuffle(p.begin(), p.end());
for (int node : p)
{
if(done[node]) continue;
mnAns = min(mnAns, bfs(node));
clear();
}
for (int node = 0; node < n; node++)
{
if(done[node]) continue;
mnAns = min(mnAns, bfs(node));
clear();
}
vector<int> cnt(n, 0);
for (int i = 0; i < n; i++)
{
cnt[i] = (ans[i] == mnAns);
}
return cnt;
}
