#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MX = 1e6;
vector<signed> find_reachable(vector<signed> r, vector<signed> u, vector<signed> v, vector<signed> c) {
int n = r.size();
int m = u.size();
vector<vector<pii> > g(1000L * MX * n);
for(int i = 0; i < m; ++i) {
g[u[i]].push_back({v[i], c[i]});
g[v[i]].push_back({u[i], c[i]});
}
vector<bool> vis, got_key;
vector<set<int> > waiting;
auto reach_dfs = [&](auto&& dfs, int node) -> void
{
if (vis[node]) {
return;
}
vis[node] = true;
// cout << "hi " << node << ' ' << r[node] << endl;
got_key[r[node]] = true;
while(!waiting[r[node]].empty()) {
if(!vis[ *waiting[r[node]].begin() ]) {
int to = *waiting[r[node]].begin();
waiting[r[node]].erase(waiting[r[node]].begin());
dfs(dfs, to);
}
else {
waiting[r[node]].erase(waiting[r[node]].begin());
}
}
for(auto [to, key] : g[node]) {
if(vis[to]) {
continue;
}
else if(!got_key[key]) {
assert(to < n);
waiting[key].insert(to);
}
else {
dfs(dfs, to);
}
}
};
vector<int> ans(n);
for(int i = 0; i < n; ++i) {
vis.assign(n, false);
got_key.assign(m, false);
waiting.assign(m, set<int>());
reach_dfs(reach_dfs, i);
ans[i] = count(vis.begin(), vis.end(), true);
// cout << i << " : ";
// for(int j = 0; j < n; ++j)
// cout << vis[j] << ' ';
// cout << " : ";
// for(int j = 0; j < m; ++j) {
// cout << got_key[j] << ' ';
// }
// cout << endl;
}
int mn = *min_element(ans.begin(), ans.end());
for(int& x : ans)
x = (x == mn);
return ans;
}
/*
7 10
0 1 1 2 2 1 2
0 1 0
0 2 0
1 2 1
1 3 0
2 3 0
3 4 1
3 5 2
4 5 0
4 6 2
5 6 1
*/
