#include <vector>
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int SZ = 303030;
struct dsu {
int par[SZ];
int sz[SZ];
void init() {
iota(par, par + SZ, 0);
fill(sz, sz + SZ, 1);
}
int find(int a) {
return par[a] = par[a] == a ? a : find(par[a]);
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
sz[b] += sz[a];
par[b] = a;
}
}
} dsu;
vector<int> find_reachable(vector<int> A, vector<int> U, vector<int> V, vector<int> B) {
int n = A.size();
int m = B.size();
vector<pii> gph[n];
for (int i = 0; i < m; i++) {
gph[U[i]].push_back({i, V[i]});
gph[V[i]].push_back({i, U[i]});
}
int ans[n]{};
bool scc[n]{};
int counter = 0;
int key[n], chc[n];
vector<pii> vec[n];
fill(key, key + n, -1);
fill(chc, chc + n, -1);
auto calc = [&](int v) {
queue<int> Q;
vector<int> vertices;
Q.push(v);
chc[v] = ++counter;
int g = dsu.find(v);
while (!Q.empty()) {
int v = Q.front();
Q.pop();
if (dsu.find(v) != g) {
v = dsu.find(v);
assert(scc[v] || dsu.sz[v] >= dsu.sz[g]);
dsu.merge(v, g);
return;
}
vertices.push_back(v);
int c = A[v];
key[c] = counter;
while (!vec[c].empty() && vec[c].back().ff == counter) {
int x = vec[c].back().ss;
vec[c].pop_back();
if (chc[x] != counter) {
Q.push(x);
chc[x] = counter;
}
}
for (auto [e, x] : gph[v]) {
if (chc[x] != counter) {
if (key[B[e]] == counter) {
Q.push(x);
chc[x] = counter;
}
else {
vec[B[e]].push_back({counter, x});
}
}
}
}
scc[g] = true;
for (int v : vertices) ans[v] = vertices.size();
};
dsu.init();
for (int v = 0; v < n; v++) {
for (auto [e, x] : gph[v]) {
if (B[e] == A[v]) {
dsu.merge(x, v);
break;
}
}
}
priority_queue<pii> pq;
for (int v = 0; v < n; v++) {
if (dsu.find(v) == v) {
pq.push({-dsu.sz[v], v});
}
}
while (!pq.empty()) {
auto [sz, v] = pq.top();
pq.pop();
sz *= -1;
if (dsu.sz[v] != sz || dsu.find(v) != v) {
continue;
}
calc(v);
int x = dsu.find(v);
if (!scc[x]) {
pq.push({-dsu.sz[x], x});
}
}
int mn = 1e9;
for (int v = 0; v < n; v++) {
if (ans[v] != 0) mn = min(mn, ans[v]);
}
vector<int> ret(n);
for (int v = 0; v < n; v++) {
if (ans[v] == mn) ret[v] = 1;
}
return ret;
}
