#include <bits/stdc++.h>
#include "keys.h"
// #include "grader.cpp"
using namespace std;
const int N = 3e5 + 10;
int n, m, ans[N], obtain[N], vis[N], mn_ans;
vector<int> key, seen[N], at_key[N], keys_seen;
vector<pair<int, int>> g[N];
void traverse(int source){
queue<int> q;
q.push(source);
vis[source] = 1;
seen[source].push_back(source);
// cout << ":: " << source << endl;
while (!q.empty()){
int v = q.front();
q.pop();
ans[source]++;
// cout << "visiting " << v << endl;
int ind = lower_bound(seen[v].begin(), seen[v].end(), source) - seen[v].begin();
if (v != source and ind < seen[v].size() and seen[v][ind] == source){
ans[source] = ans[v] - q.size();
break;
}
for (auto [k, u] : g[v]){
if (vis[u]) continue;
keys_seen.push_back(k);
if (obtain[k]){
q.push(u);
vis[u] = 1;
// cout << "pushingn " << u << endl;
seen[source].push_back(u);
}
else
at_key[k].push_back(u);
}
if (!obtain[key[v]])
keys_seen.push_back(key[v]);
obtain[key[v]] = 1;
for (int x : at_key[key[v]]){
if (!vis[x]){
vis[x] = 1;
// cout << "pushing " << x << endl;
q.push(x);
seen[source].push_back(x);
}
}
at_key[key[v]].clear();
if (ans[source] + q.size() > mn_ans)
break;
}
ans[source] += q.size();
// cout << source << " -- " << ans[source] << endl;
mn_ans = min(mn_ans, ans[source]);
for (int k : keys_seen){
at_key[k].clear();
obtain[k] = 0;
}
keys_seen.clear();
for (int v : seen[source])
vis[v] = 0;
sort(seen[source].begin(), seen[source].end());
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
key = r, n = r.size(), m = u.size(), mn_ans = n;
for (int i = 0; i < m; i ++){
g[u[i]].push_back({c[i], v[i]});
g[v[i]].push_back({c[i], u[i]});
}
for (int v = 0; v < n; v ++)
traverse(v);
vector<int> output(n);
for (int v = 0; v < n; v ++)
output[v] = (ans[v] == mn_ans);
return output;
}
