#include <iostream>
#include <vector>
#include "keys.h"
using namespace std;
vector<vector<pair<int, int>>> adj;
vector<int> foundKeys;
vector<int> vis;
vector<int> newVis;
vector<int> key_type;
int new_nodes = 1;
void dfs(int st){
if(!vis[st]) new_nodes++;
newVis[st] = 1;
vis[st] = 1;
foundKeys[key_type[st]] = 1;
for(auto i : adj[st]){
if(foundKeys[i.second] && !newVis[i.first]) dfs(i.first);
}
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
int n = r.size();
int m = c.size();
key_type = r;
vector<int> p(n, 0);
adj.assign(n, {});
for(int i = 0; i<m; i++){
adj[u[i]].push_back({v[i], c[i]});
adj[v[i]].push_back({u[i], c[i]});
}
for(int i = 0; i<n; i++){
vis.assign(n, 0);
new_nodes = 0;
foundKeys.assign(n, 0);
while(new_nodes || vis[i] == 0){
new_nodes = 0;
newVis.assign(n, 0);
dfs(i);
}
for(int j = 0; j<n; j++) if(vis[j]) p[i]++;
}
int mn = n;
for(int i = 0; i<n; i++) mn = min(mn, p[i]);
for(int i = 0; i<n; i++) p[i] = (p[i] == mn)?1:0;
return p;
}
// int main(void){
// freopen("input.txt", "r", stdin);
// int n1, m1;
// cin>>n1>>m1;
// vector<int> r1(n1);
// vector<int> u1(n1);
// vector<int> v1(n1);
// vector<int> c1(n1);
// for(int i = 0; i<n1; i++) cin>>r1[i];
// for(int i = 0; i<m1; i++){
// cin>>u1[i]>>v1[i]>>c1[i];
// }
// vector<int> ans = find_reachable(r1, u1, v1, c1);
// for(auto i : ans) cout<<i<<endl;
// }
