#include "keys.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
vi pai, tam;
set<pii> S;
int find(int x) {
if(pai[x] == x) return x;
return pai[x] = find(pai[x]);
}
void join(int x, int y) {
x = find(x);
y = find(y);
S.erase({tam[y], y});
tam[y] += tam[x];
pai[x] = y;
S.insert({tam[y], y});
}
vector<vector<pii>> edges;
vector<vi> need_key;
vi vis, keys, r, p;
int bfs(int raiz) {
queue<int> fila;
fila.push(raiz);
vi change_no = {raiz}, change_key;
int rsp = -1;
while(!fila.empty()) {
int x = fila.front();
fila.pop();
if(!keys[r[x]]) {
for(auto it : need_key[r[x]])
if(!vis[it]) vis[it] = 1, fila.push(it), change_no.pb(it);
keys[r[x]] = 1;
change_key.pb(r[x]);
need_key.clear();
}
if(find(x) != raiz) { rsp = find(x); break; }
for(auto [viz, nk] : edges[x]) {
if(vis[viz]) continue;
if(keys[nk]) vis[viz] = 1, fila.push(viz), change_no.pb(viz);
else need_key[nk].pb(viz), change_key.pb(nk);
}
}
for(auto it : change_key)
keys[it] = 0, need_key[it].clear();
for(auto it : change_no) {
if(rsp == -1) p[it] = sz(change_no);
vis[it] = 0;
}
return rsp;
}
vi find_reachable(vi R, vi u, vi v, vi c) {
int n = sz(R), m = sz(c);
pai.resize(n);
tam.resize(n, 1);
for(int i = 0; i < n; i++)
pai[i] = i, S.insert({1,i});
edges.resize(n);
need_key.resize(n);
vis.resize(n);
keys.resize(n);
p.resize(n,n+1);
r = R;
for(int i = 0; i < m; i++)
edges[u[i]].pb({v[i], c[i]}), edges[v[i]].pb({u[i], c[i]});
while(!S.empty()) {
int x = (*S.begin()).sc, y = bfs(x);
S.erase(S.begin());
if(y != -1) join(x,y);
}
int minP = n+1;
for(int i = 0; i < n; i++) minP = min(minP, p[i]);
vi ans(n);
for(int i = 0; i < n; i++)
ans[i] = minP == p[i];
return ans;
}
