#include <vector>
#include <iostream>
#include <array>
#include <map>
#define ll long long
using namespace std;
ll n, m, f, cnt, A[300000], sz[300000], szout[300000], done[300000], P[300000];
vector <ll> V;
bool visited[300000];
map <ll, ll> mp, keys[300000], edge[300000];
map <ll, vector<ll>> out[300000];
ll dsu(ll u) {
if (P[u] == u) return u;
else return P[u] = dsu(P[u]);
}
void merge(ll u, ll v) {
if (edge[u].size() < edge[v].size()) {
for (auto [x, y] : edge[u]) ++edge[v][dsu(x)];
swap(edge[u], edge[v]);
}
else {
for (auto [x, y] : edge[v]) ++edge[u][dsu(x)];
}
if (keys[u].size()+szout[v] < keys[v].size()+szout[u]) {
for (auto [x, y] : keys[u]) {
if (out[v].count(x)) {
for (auto g : out[v][x]) ++edge[u][dsu(g)];
}
keys[v].insert({x, y});
}
swap(keys[u], keys[v]);
for (auto [x, y] : out[v]) {
if (keys[u].count(x)) {
for (auto g : y) ++edge[u][dsu(g)];
}
else out[u].insert({x, y});
}
}
else {
for (auto [x, y] : keys[v]) {
if (out[u].count(x)) {
for (auto g : out[u][x]) ++edge[u][dsu(g)];
}
keys[u].insert({x, y});
}
for (auto [x, y] : out[u]) {
if (keys[u].count(x)) {
for (auto g : y) ++edge[u][dsu(g)];
}
else out[v].insert({x, y});
}
swap(out[u], out[v]);
}
sz[u] += sz[v];
szout[u] += szout[v];
P[v] = u;
}
void dfs(ll u) {
done[u] = cnt;
visited[u] = 1;
V.push_back(u);
//cout << u << endl;
for (auto [z, y] : edge[u]) {
ll x = dsu(z);
if (dsu(u) == x || (done[x] != -1 && done[x] != cnt)) continue;
if (visited[x]) {
while (!V.empty() && V.back() != x) {
auto v = dsu(V.back());
V.pop_back();
merge(x, v);
//cout << v << " ";
}
//cout << x << endl;
}
if (done[x] == -1) {
//cout << u << "->" << x << endl;
dfs(x);
}
}
visited[u] = 0;
if (!V.empty() && V.back() == dsu(u)) V.pop_back();
}
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(), cnt = 0;
mp.clear();
for (int i=0; i<n; ++i) {
P[i] = i;
done[i] = -1;
sz[i] = 1;
++keys[i][r[i]];
}
for (int i=0; i<m; ++i) {
if (c[i] == r[u[i]]) ++edge[u[i]][v[i]];
else out[u[i]][c[i]].push_back(v[i]), ++szout[u[i]];
if (c[i] == r[v[i]]) ++edge[v[i]][u[i]];
else out[v[i]][c[i]].push_back(u[i]), ++szout[v[i]];
}
vector <int> F(n, 0);
bool ok = 0;
for (int i=0; i<n; ++i) {
if (edge[i].empty()) {
F[i] = ok = 1;
}
}
if (ok) return F;
for (int i=0; i<n; ++i) {
if (done[i] == -1) {
dfs(i);
++cnt;
}
}
ll f = 1e18;
for (int i=0; i<n; ++i) {
++mp[dsu(i)];
}
for (auto [x, y] : mp) {
for (auto it = edge[x].begin(); it != edge[x].end();) {
auto nx = next(it);
ll z = dsu(it->first);
if (x == z) edge[x].erase(it);
it = nx;
}
}
for (int i=0; i<n; ++i) {
auto x = dsu(i);
if (edge[x].empty()) f = min(f, sz[x]);
}
for (int i=0; i<n; ++i) {
auto x = dsu(i);
if (edge[x].empty() && sz[x] == f) F[i] = 1;
else F[i] = 0;
}
return F;
}
