#include <bits/stdc++.h>
#include "keys.h"
using namespace std;
#define ll int
#define F first
#define S second
#define pb push_back
#define sz(x) (ll)x.size()
#define inf 1000000000
typedef vector <ll> vi;
typedef pair <ll,ll> ii;
typedef vector <ii> vii;
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;
void printVct(vi &v){
for (ll i =0; i<sz(v); i++){
cout<<v[i]<<" ";
}
cout<<endl;
}
vector <vii> adj;
vi vis;
ll bfs(ll s, vi &r){
ll n = sz(r);
queue <ll> q;
vector < stack <ll> > waiting_stacks(n);
vi found_keys(n);
found_keys[r[s]] = 1;
q.push(s);
ll ans = 0;
while (!q.empty()){
ll f = q.front();
q.pop();
if (vis[f]) continue;
vis[f] = 1;
ans++;
if (!found_keys[r[f]]){
found_keys[r[f]] = 1;
while (!waiting_stacks[r[f]].empty()){
q.push(waiting_stacks[r[f]].top());
waiting_stacks[r[f]].pop();
}
}
for (ll i =0; i<sz(adj[f]); i++){
ii c = adj[f][i];
if (!vis[c.F]){
if (found_keys[c.S]){
q.push(c.F);
}
else{
waiting_stacks[c.S].push(c.F);
}
}
}
}
return ans;
}
vi find_reachable(vi r, vi u, vi v, vi c) {
ll n = sz(r);
ll m = sz(c);
vi ans(n, 0);
adj.assign(n, vii());
for(ll i =0; i<m; i++){
adj[u[i]].pb(ii(v[i], c[i]));
adj[v[i]].pb(ii(u[i], c[i]));
}
vi connections(n);
ll mini = inf;
for (ll i =0; i<n; i++){
vis.assign(n, 0);
connections[i] = bfs(i, r);
mini = min(connections[i], mini);
}
// printVct(connections);
for (ll i =0; i<n; i++){
ans[i] = (connections[i] == mini);
}
return ans;
}
/*
3 1
0 0 0
0 1 0
*/
