#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 3e5;
map<int, vector<int>>* all_edges[MAXN];
vector<int> edges[MAXN];
set<int>* colors[MAXN];
int vis[MAXN];
bool dead[MAXN];
int uf[MAXN];
int edgecount[MAXN];
int sz[MAXN];
int n, m;
int find(int i) {
return uf[i] == i ? i : uf[i] = find(uf[i]);
}
vector<int> stck;
void make_edges(int i, vector<int> &e) {
for (int v: e) edges[i].push_back(v);
}
vector<int> &get(map<int, vector<int>> *mp, int v) {
if (mp->find(v) == mp->end()) {
vector<int> nv;
mp->insert(pair<int, vector<int>>(v, nv));
}
return mp->at(v);
}
void merge(int i, int j) {
i = find(i);
j = find(j);
assert(i != j);
if (i == j) return;
if (edgecount[j] > edgecount[i]) swap(i, j);
edgecount[i] += edgecount[j];
uf[j] = i;
sz[i] += sz[j];
for (auto it: *all_edges[j]) {
if (colors[i]->find(it.first) != colors[i]->end()) make_edges(i, it.second);
else for (int val: it.second) get(all_edges[i], it.first).push_back(val);
}
all_edges[j]->clear();
for (int v: edges[j]) edges[i].push_back(v);
edges[j].clear();
for (int c: *colors[j]) {
make_edges(i, get(all_edges[i], c));
all_edges[i]->erase(c);
colors[i]->insert(c);
}
colors[j]->clear();
}
void dfs(int cur) {
vis[cur] = 1;
stck.push_back(cur);
bool f = 0;
for (int v: edges[cur]) {
int nxt = find(v);
if (vis[nxt] == 2) {
stck.pop_back();
dead[cur] = 1;
// assert(false);
f = 1;
break;
}
if (nxt == cur) continue;
if (vis[nxt] == 1) {
while (stck.back() != nxt) {
merge(nxt, stck.back());
stck.pop_back();
}
stck.pop_back();
nxt = find(nxt);
dfs(nxt);
f = 1;
break;
}
else {
dfs(nxt);
f = 1;
if (!stck.empty() && stck.back() == cur) {
// assert(false);
dead[cur] = 1;
stck.pop_back();
}
break;
}
}
vis[cur] = 2;
if (!f) {
stck.pop_back();
return;
}
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
n = r.size();
m = u.size();
for (int i = 0; i < n; i++) {
colors[i] = new set<int>();
colors[i]->insert(r[i]);
all_edges[i] = new map<int, vector<int>>();
}
for (int i = 0; i < m; i++) {
if (r[u[i]] == c[i]) edges[u[i]].push_back(v[i]);
else get(all_edges[u[i]], c[i]).push_back(v[i]);
swap(u[i], v[i]);
if (r[u[i]] == c[i]) edges[u[i]].push_back(v[i]);
else get(all_edges[u[i]], c[i]).push_back(v[i]);
edgecount[u[i]]++;
edgecount[v[i]]++;
}
iota(uf, uf+n, 0);
fill(sz, sz+n, 1);
for (int i = 0; i < n; i++) if (vis[i] == 0) dfs(i);
vector<int> ans;
int small = n;
for (int i = 0; i < n; i++) {
if (dead[find(i)] || sz[find(i)] > small) continue;
if (sz[find(i)] < small) {
small = sz[find(i)];
ans.clear();
}
if (sz[find(i)] == small) ans.push_back(i);
}
vector<int> res(n, 0);
for (int v: ans) res[v] = 1;
return res;
}
