#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef pair<int, int> pii;
#define MAX 301010
int N, M;
int cycle_chk[MAX];
int find_cycle(int v) {
if (cycle_chk[v] == v) return v;
else return cycle_chk[v] = find_cycle(cycle_chk[v]);
}
void merge_cycle(int u, int v) {
u = find_cycle(u);
v = find_cycle(v);
cycle_chk[u] = v;
}
int p[MAX];
int num[MAX];
set<int> keys[MAX];
queue<int> adj[MAX];
map<int, vector<int>> mp[MAX];
int nxt[MAX];
vector<int> subv[MAX];
#define exists(st, v) (st.find(v) != st.end())
int find(int v) {
if (p[v] == v) return v;
return p[v] = find(p[v]);
}
queue<pii> lst;
int mn;
vector<int> mlist;
int pp[MAX];
int find_last(int v) {
if (pp[v] == v) return v;
return pp[v] = find(pp[v]);
}
void merge_last(int u, int v) {
u = find_last(u);
v = find_last(v);
pp[u] = v;
}
void add_lst(int u, int v) {
if (find_last(u) == find_last(v)) return;
merge_last(u, v);
lst.emplace(u, v);
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
if (keys[u].size() > keys[v].size()) swap(u, v);
p[u] = v;
if (subv[u].size() > subv[v].size()) swap(subv[u], subv[v]);
for (auto x : subv[u]) subv[v].push_back(x);
num[v] += num[u];
for (auto x : keys[u]) {
keys[v].insert(x);
if (exists(mp[v], x)) {
for (auto nxt : mp[v][x]) adj[v].push(find(nxt));
mp[v].erase(x);
}
}
for (auto& [x, vec] : mp[u]) {
if (exists(keys[v], x)) for (auto nxt : vec) adj[v].push(find(nxt));
else for (auto nxt : vec) mp[v][x].push_back(find(nxt));
}
while (adj[u].size()) adj[v].push(adj[u].front()), adj[u].pop();
while (adj[v].size()) {
int t = adj[v].front();
if (find(t) != find(v)) {
nxt[v] = t;
if (find_cycle(t) == find_cycle(v)) {
int debug_iters = 0;
int loc = t;
int pv = t;
while (find(loc) != find(v)) {
debug_iters++;
assert(debug_iters < 400000);
loc = nxt[loc];
loc = find(loc);
add_lst(loc, pv);
pv = loc;
}
}
else merge_cycle(t, v);
break;
}
else adj[v].pop();
}
if (adj[v].empty()) {
if (mn > num[v]) {
mlist = subv[v];
mn = num[v];
}
else if (mn == num[v]) mlist.insert(mlist.end(), subv[v].begin(), subv[v].end());
}
}
vector<int> radj[MAX];
std::vector<int> find_reachable(std::vector<int> R, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
N = R.size();
M = U.size();
int i;
for (i = 0; i < N; i++) p[i] = i, num[i] = 1, cycle_chk[i] = i, keys[i].emplace(R[i]), subv[i].push_back(i), pp[i] = i;
mn = N;
for (i = 0; i < M; i++) radj[U[i]].push_back(i), radj[V[i]].push_back(i);
auto to = [&](int v, int e) {
return U[e] + V[e] - v;
};
for (i = 0; i < N; i++) {
for (auto e : radj[i]) {
if (C[e] == R[i]) adj[i].emplace(to(i, e));
else mp[i][C[e]].push_back(to(i, e));
}
}
for (i = 0; i < N; i++) {
nxt[i] = -1;
if (adj[i].size()) nxt[i] = adj[i].front();
}
for (i = 0; i < N; i++) {
if (~nxt[i]) {
int t = nxt[i];
if (find_cycle(t) == find_cycle(i)) {
int loc = t;
int pv = t;
while (find(loc) != find(i)) {
loc = nxt[loc];
loc = find(loc);
add_lst(loc, pv);
pv = loc;
}
}
else merge_cycle(i, t);
}
else {
mn = 1;
mlist.push_back(i);
}
}
while (lst.size()) {
int u, v;
tie(u, v) = lst.front();
lst.pop();
merge(u, v);
}
vector<int> ansv(N);
for (auto p : mlist) ansv[p] = 1;
return ansv;
}
