#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 3e5+10, MOD = 1e9+7;
struct DSU {
vector<int> par, sz;
DSU(int n): par(n) {
iota(par.begin(), par.end(), 0);
sz.assign(n, 1);
}
int find_set(int v) {
return v == par[v] ? v : par[v] = find_set(par[v]);
}
bool union_sets(int a, int b) {
if ((a = find_set(a)) == (b = find_set(b))) return false;
if (sz[a] < sz[b]) swap(a, b);
par[b] = a, sz[a] += sz[b], sz[b] = 0;
return true;
}
};
int n, m, my_out[N];
int par[N];
vector<int> st[N];
set<int> has[N];
vector<ar<int, 2>> adj[N];
void merge(int a, int b) {
a = par[a], b = par[b];
if (a == b) return;
if (sz(st[a]) < sz(st[b])) swap(a, b);
for (int x : st[b]) {
st[a].push_back(x);
par[x] = a;
}
st[b].clear();
for (int x : has[b]) {
has[a].insert(x);
}
has[b].clear();
for (auto nxt : adj[b]) {
adj[a].push_back(nxt);
}
adj[b].clear();
}
int get_out(int c) {
c = par[c];
for (auto [nxt, w] : adj[c]) {
if (par[nxt] != c && has[c].count(w)) {
return par[nxt];
}
}
return -1;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
n = sz(r), m = sz(u);
memset(my_out, -1, sizeof(my_out));
for (int i = 0; i < n; i++) {
par[i] = i;
st[i].push_back(i);
has[i].insert(r[i]);
}
for (int i = 0; i < m; i++) {
adj[u[i]].push_back({v[i], c[i]});
adj[v[i]].push_back({u[i], c[i]});
}
DSU d(n);
for (int root = 0; root < n; root++) {
my_out[par[root]] = get_out(root);
while (my_out[par[root]] != -1) {
if (d.union_sets(root, my_out[par[root]])) {
break;
} else {
vector<int> use{par[my_out[par[root]]]};
while (use.back() != par[root]) {
use.push_back(par[my_out[use.back()]]);
}
use.pop_back();
for (int x : use) {
merge(x, root);
}
my_out[par[root]] = get_out(root);
}
}
}
int best = MOD;
for (int i = 0; i < n; i++) {
int c = par[i];
if (my_out[c] == -1) {
best = min(best, sz(st[c]));
}
}
vector<int> ans(n);
for (int i = 0; i < n; i++) {
int c = par[i];
if (my_out[c] == -1 && sz(st[c]) == best) {
ans[i] = 1;
}
}
return ans;
}
