#include <bits/stdc++.h>
#include "keys.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int LOG = 20;
struct SCC {
vector<vector<int>> adj, vadj;
stack<int> s;
vector<int> scc;
vector<bool> vis;
vector<int> parent;
SCC(int n) {
parent.resize(n);
for (int i=0; i<n; i++) {
parent[i] = i;
}
}
void init(int n) {
adj.resize(n);
vadj.resize(n);
vis.assign(n, false);
for (int i=0; i<n; i++) {
adj[i].clear();
vadj[i].clear();
}
}
void add(int a, int b) {
adj[a].push_back(b);
vadj[b].push_back(a);
}
void dfs1(int n) {
vis[n] = true;
for (auto x : adj[n]) {
if (!vis[x]) {
dfs1(x);
}
}
s.push(n);
}
void dfs2(int n) {
vis[n] = true;
scc.push_back(n);
for (auto x : vadj[n]) {
if (!vis[x]) {
dfs2(x);
}
}
}
void process(int n) {
vis.assign(n, false);
for (int i=0; i<n; i++) {
if (!vis[i]) {
dfs1(i);
}
}
vis.assign(n, false);
while (!s.empty()) {
int u = s.top();
s.pop();
if (!vis[u]) {
scc.clear();
dfs2(u);
for (auto x : scc) {
parent[x] = scc[0];
}
}
}
}
};
vector<int> find_reachable(vector<int> r, vector<int> U, vector<int> V, vector<int> C) {
int n = r.size();
int m = U.size();
vector<vector<pii>> adj(n);
vector<int> p(n, 0);
U.resize(2*m);
V.resize(2*m);
C.resize(2*m);
for (int i=m; i<2*m; i++) {
U[i] = V[i-m];
V[i] = U[i-m];
C[i] = C[i-m];
}
m *= 2;
SCC kos(n);
for (int t=0; t<LOG; t++) {
vector<set<int>> keys(n);
for (int i=0; i<n; i++) {
keys[kos.parent[i]].insert(r[i]);
}
kos.init(n);
for (int i=0; i<m; i++) {
int u = U[i];
int v = V[i];
int c = C[i];
if (kos.parent[u] == kos.parent[v] || keys[kos.parent[u]].count(c)) {
kos.add(u, v);
}
}
kos.process(n);
}
vector<int> sz(n, 0);
for (int i=0; i<n; i++) {
sz[kos.parent[i]]++;
}
vector<bool> valid(n, true);
vector<set<int>> keys(n);
for (int i=0; i<n; i++) {
keys[kos.parent[i]].insert(r[i]);
}
for (int i=0; i<m; i++) {
int u = U[i];
int v = V[i];
int c = C[i];
if (kos.parent[u] != kos.parent[v] && keys[kos.parent[u]].count(c)) {
valid[kos.parent[u]] = false;
}
}
int mn = 1e9;
for (int i=0; i<n; i++) {
if (valid[kos.parent[i]]) mn = min(mn, sz[kos.parent[i]]);
}
vector<int> ans(n, 0);
for (int i=0; i<n; i++) {
if (valid[kos.parent[i]] && sz[kos.parent[i]] == mn) {
ans[i] = 1;
}
}
return ans;
}
