#include <bits/stdc++.h>
#include "keys.h"
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], obtained;
vector<pair<int, int>> g[N];
void traverse(int source){
queue<int> q;
q.push(source);
while (!q.empty()){
int v = q.front();
ans[source]++;
int ind = lower_bound(seen[v].begin(), seen[v].end(), source) - seen[v].begin();
if (ind < seen[v].size() and seen[v][ind] == source){
ans[source] = ans[v];
break;
}
for (auto [k, u] : g[v]){
if (vis[u]) continue;
if (obtain[k]){
q.push(u);
vis[u] = 1;
seen[source].push_back(u);
}
else
at_key[k].push_back(u);
}
if (!obtain[key[v]])
obtained.push_back(key[v]);
obtain[key[v]] = 1;
for (int x : at_key[key[v]]){
if (!vis[x]){
vis[x] = 1;
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();
mn_ans = min(mn_ans, ans[source]);
for (int k : obtained){
at_key[k].clear();
obtain[k] = 0;
}
obtained.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;
}
