#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
struct nod {
set<int> Noduri;
set<int> Cul;
set<ii> MuchiiActive;
set<ii> MuchiiFol;
set<ii> MuchiiInactive; // (cul, to)
///multiset<int> Wishlist; < pt optimizare
bool empty() { return MuchiiActive.empty(); }
ii get_muchie() {
auto it = *MuchiiActive.begin();
MuchiiActive.erase(it);
MuchiiFol.insert(it);
return it;
}
int size() { return int(Noduri.size()); }
void add_edge(int to, int c) {
if(Cul.count(c)) {
MuchiiActive.insert({c, to});
} else {
MuchiiInactive.insert({c, to});
}
}
};
void join_nod(nod &a, nod &b) {
///va pune info din b in a
for(auto it : b.Noduri)
a.Noduri.insert(it);
for(auto it : b.Cul)
a.Cul.insert(it);
for(auto it : b.MuchiiActive)
a.MuchiiActive.insert(it);
for(auto it : b.MuchiiInactive)
b.MuchiiInactive.insert(it);
vector<ii> A;
for(auto [cul, to] : a.MuchiiInactive) {
if(a.Cul.count(cul)) {
A.push_back({cul, to});
}
}
for(auto it : A) {
a.MuchiiInactive.erase(it);
a.MuchiiActive.insert(it);
}
}
struct DSU {
int n;
vi e;
vector<nod> V;
DSU(int N, vector<nod> &V0) : n(N), e(N, -1), V(V0) {}
int repr(int u) {
while(e[u] >= 0) u = e[u];
return u;
}
void join(int u, int v) {
u = repr(u);
v = repr(v);
if(u == v) return;
if(e[u] >= e[v]) swap(u, v);
e[u] += e[v];
e[v] = u;
join_nod(V[u], V[v]);
}
vi solve() {
vi viz(n, 0);
vi S;
function<void(int)> dfs = [&](int u) {
u = repr(u);
if(viz[u] == 2) return;
if(viz[u] == 1) {
while(repr(S.back()) != repr(u)) {
join(u, S.back());
S.pop_back();
}
S.pop_back();
}
u = repr(u);
viz[u] = 1;
S.push_back(u);
while(!V[u].empty()) {
auto [cul, to] = V[u].get_muchie();
if(repr(to) == u) continue;
dfs(to);
u = repr(u); /// poate au existat joinuri
}
if(!S.empty() && S.back() == u)
S.pop_back();
viz[u] = 2;
};
for(int i = 0; i < n; ++i)
if(!viz[i]) dfs(i);
int mi = n;
vi capat(n, 0);
for(int i = 0; i < n; ++i) {
if(e[i] < 0) {
capat[i] = 1;
for(auto [c, to] : V[i].MuchiiFol) {
if(repr(to) != i) {
capat[i] = 0;
}
}
if(capat[i]) {
mi = min(mi, V[i].size());
}
}
}
vi re(n, 0);
for(int i = 0; i < n; ++i) {
if(capat[repr(i)] && V[repr(i)].size() == mi) {
re[i] = 1;
}
}
return re;
}
};
vi find_reachable(vi r, vi U, vi V, vi C) {
int n = int(r.size()), m = int(U.size());
vector<nod> V0(n);
for(int i = 0; i < n; ++i) {
V0[i].Noduri.insert(i);
V0[i].Cul.insert(r[i]);
}
for(int i = 0; i < m; ++i) {
V0[U[i]].add_edge(V[i], C[i]);
V0[V[i]].add_edge(U[i], C[i]);
}
DSU Sol(n, V0);
return Sol.solve();
}
