#include <bits/stdc++.h>
#include "keys.h"
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
struct DSU_Path {
vector<int> par;
int n;
DSU_Path() { }
DSU_Path(int _n) {
n = _n;
par.resize(n);
iota(par.begin(), par.end(), 0);
}
int find(int u) {
return par[u] = (u == par[u] ? u : find(par[u]));
}
void merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
par[u] = v;
}
};
struct SCC {
int n;
vector<int> par, sz;
vector<set<int>> all;
vector<set<pair<int, int>>> good, bad;
SCC(int _n) {
n = _n;
sz.assign(n, 1);
par.resize(n);
all.resize(n);
good.resize(n), bad.resize(n);
iota(par.begin(), par.end(), 0);
}
int find(int u) {
return par[u] = (u == par[u] ? u : find(par[u]));
}
void merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (sz[u] > sz[v]) swap(u, v);
sz[v] += sz[u];
par[u] = v;
for (int k : all[u]) {
while (true) {
auto it = bad[v].lower_bound({k, -5});
if (it != bad[v].end() && (*it).first == k) {
bad[v].erase(*it);
good[v].insert(*it);
} else {
break;
}
}
all[v].insert(k);
}
all[u].clear();
for (auto e : good[u]) good[v].insert(e);
good[u].clear();
for (auto e : bad[u]) {
if (all[u].count(e.first)) good[v].insert(e);
else bad[v].insert(e);
}
bad[u].clear();
}
};
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
int n = r.size();
vector<int> succ(n);
DSU_Path paths = DSU_Path(n);
SCC scc = SCC(n);
for (int i = 0; i < n; i++) succ[i] = i;
for (int i = 0; i < n; i++) {
scc.all[i].insert(r[i]);
}
for (int i = 0; i < u.size(); i++) {
if (scc.all[u[i]].count(c[i])) scc.good[u[i]].insert({c[i], v[i]});
else scc.bad[u[i]].insert({c[i], v[i]});
if (scc.all[v[i]].count(c[i])) scc.good[v[i]].insert({c[i], u[i]});
else scc.bad[v[i]].insert({c[i], u[i]});
}
for (int i = 0; i < n; i++) {
if (succ[i] != i) continue;
int root = scc.find(i);
while (!scc.good[root].empty()) {
auto [c, v] = *scc.good[root].begin();
scc.good[root].erase(scc.good[root].begin());
if (paths.find(root) != paths.find(v)) {
succ[scc.find(i)] = v;
paths.merge(paths.find(i), v);
break;
} else {
v = scc.find(v), root = scc.find(root);
while (v != root) {
scc.merge(v, root);
v = succ[v];
}
}
root = scc.find(root);
}
}
int mn = n;
set<int> good_components;
for (int i = 0; i < n; i++) {
if (succ[i] == i) mn = min(mn, scc.sz[scc.find(i)]);
}
for (int i = 0; i < n; i++) {
if (succ[i] == i && scc.sz[scc.find(i)] == mn) good_components.insert(scc.find(i));
}
vector<int> good;
for (int i = 0; i < n; i++) {
if (good_components.count(scc.find(i))) good.push_back(i);
}
vector<int> ans(n);
for (int i : good) ans[i] = 1;
return ans;
}
