#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <numeric>
#include <queue>
#include <limits>
using namespace std;
using vi = vector<int>;
struct DsuStrong {
vector<map<int, vi>> edg;
vector<set<int>> keys;
vector<queue<int>> q;
vector<int> rnk, par;
DsuStrong(int n) : edg(n), keys(n), q(n), rnk(n, 1), par(n) {
iota(par.begin(), par.end(), 0);
}
int root(int v) {
return v == par[v] ? v : root(par[v]);
}
bool same(int a, int b) {
return root(a) == root(b);
}
int any_edge(int v) {
if (q[v].empty()) return -1;
int res = q[v].front();
q[v].pop();
return root(res);
}
bool unite(int a, int b) {
a = root(a), b = root(b);
if (a == b) {
return false;
} else {
if (rnk[a] < rnk[b]) swap(a, b);
rnk[a] += rnk[b];
par[b] = a;
for (int x : keys[b]) {
auto [it, added] = keys[a].insert(x);
if (added) {
for (int u : edg[a][x]) q[a].push(u);
}
}
for (auto [c, v] : edg[b]) {
for (int x : v) edg[a][c].push_back(x);
if (keys[a].count(c)) {
for (int x : v) q[a].push(x);
}
}
return true;
}
}
};
struct Dsu {
vector<int> rnk, par;
Dsu(int n) : rnk(n, 1), par(n) {
iota(par.begin(), par.end(), 0);
}
int root(int v) {
return v == par[v] ? v : root(par[v]);
}
bool same(int a, int b) {
return root(a) == root(b);
}
bool unite(int a, int b) {
a = root(a), b = root(b);
if (a == b) {
return false;
} else {
if (rnk[a] < rnk[b]) swap(a, b);
rnk[a] += rnk[b];
par[b] = a;
return true;
}
}
};
vi find_reachable(vi r, vi u, vi v, vi c) {
const int n = r.size(), m = c.size();
DsuStrong dsu_strong(n);
Dsu dsu(n);
for (int i = 0; i < n; ++i) {
dsu_strong.keys[i].insert(r[i]);
}
for (int i = 0; i < m; ++i) {
for (int t = 2; t--; ) {
dsu_strong.edg[u[i]][c[i]].push_back(v[i]);
if (r[u[i]] == c[i]) dsu_strong.q[u[i]].push(v[i]);
swap(u[i], v[i]);
}
}
vector<int> par(n, -1);
queue<int> q;
for (int i = 0; i < n; ++i) q.push(i);
while (!q.empty()) {
const int v = q.front(); q.pop();
const int u = dsu_strong.any_edge(v);
// cout << "Pop v=" << v << ", with edge " << u << endl;
if (u == -1) continue;
if (dsu.same(v, u)) {
int to = -1;
for (int w = u; w != v; w = to) {
to = dsu_strong.root(par[w]);
dsu_strong.unite(w, v);
// cout << "unite " << w << " and " << v << " (strong)" << endl;
}
par[v] = v;
int new_root = dsu_strong.root(v);
par[new_root] = -1;
q.push(new_root);
} else {
par[v] = u;
dsu.unite(v, u);
// cout << "unite " << u << " and " << v << " (tree)" << endl;
}
}
vi roots, ans(n);
int sz = numeric_limits<int>::max();
for (int i = 0; i < n; ++i) {
if (par[i] != -1) continue;
int cur = dsu_strong.rnk[i];
if (cur < sz) roots.clear(), sz = cur;
if (cur == sz) roots.push_back(i);
}
vector<char> allowed(n);
for (int x : roots) allowed[x] = true;
for (int i = 0; i < n; ++i) {
if (allowed[dsu_strong.root(i)]) ans[i] = 1;
}
return ans;
}
