#include "keys.h"
#include "bits/stdc++.h"
using namespace std;
using g_t = vector<unordered_map<int, vector<int>>>;
using g_t2 = vector<vector<int>>;
int find(int a, vector<int> &p) {
if (p[a] == a) return a;
return p[a] = find(p[a], p);
}
bool unite(int a, int b, vector<int> &p, g_t &g, vector<int> &si, vector<unordered_set<int>> &in) {
a = find(a, p), b = find(b, p);
if (a == b) return false;
if (si[a] < si[b]) swap(a, b);
p[b] = a;
si[a] += si[b];
in[a].insert(in[b].begin(), in[b].end());
for (auto [co, e]: g[b]) {
for (auto ed: e) {
if (find(ed, p) != a)
g[a][co].push_back(ed);
}
}
return true;
}
void poO(int n, int &t, g_t &g, g_t2 &rev, vector<unordered_set<int>> &whi, vector<int> &poOv, vector<int> &p) {
n = find(n, p);
if (poOv[n] != -1) return;
poOv[n] = -2;
for (auto e: whi[n]) {
if (g[n].find(e) != g[n].end()) {
for (auto f: g[n][e]) {
f = find(f, p);
rev[f].push_back(n);
poO(f, t, g, rev, whi, poOv, p);
}
}
}
poOv[n] = t++;
}
void markDfs(int n, int co, g_t2 &g, vector<int>& col, vector<int> &p) {
n = find(n, p);
if (col[n] != -1) return;
col[n] = co;
for (auto e: g[n]) {
e = find(e, p);
markDfs(e, co, g, col, p);
}
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
int n = r.size();
g_t in(r.size());
for (int i = 0; i < u.size(); ++i) {
in[u[i]][c[i]].push_back(v[i]);
in[v[i]][c[i]].push_back(u[i]);
}
vector<int> p(n), si(n, 1);
iota(p.begin(), p.end(), 0);
vector<unordered_set<int>> whi(n);
for (int i = 0; i < n; ++i) {
whi[i].insert(r[i]);
}
bool ch = true;
while (ch) {
ch = false;
int t = 0;
vector<int> pos(n, -1);
g_t2 gT(n);
for (int i = 0; i < n; ++i) {
poO(i, t, in, gT, whi, pos, p);
}
vector<int> o(n);
std::iota(o.begin(), o.end(), 0);
std::sort(o.begin(), o.end(), [&](int l, int r) { return pos[l] > pos[r]; });
vector<int> col(n, -1);
for (int i = 0; i < n; ++i) {
if (pos[o[i]] != -1) {
markDfs(o[i], o[i], gT, col, p);
}
}
for (int i = 0; i < n; ++i) {
if (col[i] != -1) ch = unite(col[i], i, p, in, si, whi) || ch;
}
}
vector<int> re(n, 1);
for (int i = 0; i < n; ++i) {
if (i == find(i, p)) {
for (auto e: whi[i]) {
if (in[i].find(e) != in[i].end()) {
for (auto f: in[i][e]) {
f = find(f, p);
re[i] = re[i] && f == i;
}
}
}
}
}
int mi = n;
for (int i = 0; i < n; ++i) {
if (re[find(i, p)]) {
mi = min(mi, si[find(i, p)]);
}
}
for (int i = 0; i < n; ++i) {
re[i] = re[find(i, p)] && mi == si[find(i, p)];
}
return re;
}
