#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];
set<pii> 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 mcnt[MAX]; //max move cnt
int merge_two(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return u;
if (mcnt[u] >= mcnt[v]) swap(u, v);
mcnt[v] = max(mcnt[v], mcnt[u] + 1);
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);
while (1) {
auto it = mp[v].lower_bound(pii(x, -1));
if (it == mp[v].end() || it->first != x) break;
adj[v].emplace(it->second);
mp[v].erase(it);
}
}
for (auto& [k, nv] : mp[u]) {
if (exists(keys[v], k)) adj[v].push(nv);
else mp[v].insert(pii(k, nv));
}
while (adj[u].size()) adj[v].push(adj[u].front()), adj[u].pop();
return v;
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
int loc = v;
int m = v;
vector<int> all;
while (find(loc) != find(u)) {
loc = find(nxt[loc]);
all.push_back(loc);
}
for (auto x : all) v = merge_two(v, x);
while (adj[v].size()) {
int t = adj[v].front();
if (find(t) != find(v)) {
nxt[v] = t;
if (find_cycle(t) == find_cycle(v)) lst.emplace(v, t);
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);
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].emplace(C[e], 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)) lst.emplace(i, t);
else merge_cycle(i, t);
}
else {
mn = 1;
mlist.push_back(i);
}
}
int iters = 0;
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;
}
