#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<pair<int, int>>> v;
vector<vector<int>> rev;
vector<vector<int>> g;
vector<vector<int>> now;
vector<bool> used;
vector<int> ord;
vector<int> comp;
vector<int> sz;
vector<map<int, int>> color;
int n;
void dfs(int x) {
used[x] = 1;
for (auto to : g[x]) {
if (used[to])
continue;
dfs(to);
}
ord.push_back(x);
}
void go(int x, int nw) {
comp[x] = nw;
for (auto to : rev[x]) {
if (comp[to] != -1)
continue;
go(to, nw);
}
}
int condensate(int n) {
rev.clear();
rev.resize(n);
used.resize(n);
comp.resize(n);
fill(used.begin(), used.end(), 0);
fill(comp.begin(), comp.end(), -1);
ord.clear();
for (int i = 0; i < n; i++) {
for (auto to : g[i]) {
rev[to].push_back(i);
}
}
for (int i = 0; i < n; i++) {
if (!used[i]) {
dfs(i);
}
}
reverse(ord.begin(), ord.end());
int nw = 0;
// cout << "ord: ";
for (auto i : ord) {
// cout << i << " ";
if (comp[i] == -1) {
// cout << i << " " << nw << "go\n";
go(i, nw);
nw++;
}
}
// for (int i = 0; i < n; i++) {
// cout << comp[i] << " ";
// }
// cout << "\n";
return nw;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
vector<int> ans(r.size(), 0), p(r.size(), 0), keys(r.size());
queue<int> q;
n = r.size();
::v.resize(n);
used.resize(n);
now.resize(n);
g.resize(n);
int mn = n + 1;
// cout << n << "\n";
for (int i = 0; i < (int)u.size(); i++) {
// cout << u[i] << "\n";
::v[u[i]].push_back({v[i], c[i]});
::v[v[i]].push_back({u[i], c[i]});
}
for (int i = 0; i < n; i++) {
for (auto [to, nd] : ::v[i]) {
if (nd == r[i]) {
g[i].push_back(to);
// cout << "add " << i << " " << to << "\n";
}
}
}
int C = condensate(n);
vector<int> comp0;
sz.resize(C);
color.resize(C);
fill(sz.begin(), sz.end(), 0);
g.clear();
g.resize(C);
for (int i = 0; i < n; i++) {
sz[comp[i]]++;
color[comp[i]][r[i]] = 1;
// cout << i << " comp " << comp[i] << "\n";
}
for (int i = 0; i < n; i++) {
for (auto [to, nd] : ::v[i]) {
if (comp[to] != comp[i] && color[comp[i]][nd]) {
// cout << "add " << comp[i] << " " << comp[to] << "\n";
g[comp[i]].push_back(comp[to]);
}
}
}
// cout << "_____\n";
comp0 = comp;
int C2 = condensate(C);
vector<int> sz2(C2, 0);
vector<int> leaf(C2, 1);
for (int i = 0; i < C; i++) {
sz2[comp[i]] += sz[i];
// cout << i << " comp " << comp[i] << "\n";
}
for (int i = 0; i < C; i++) {
for (auto to : g[i]) {
if (comp[to] != comp[i]) {
leaf[comp[i]] = 0;
}
}
}
// cout << "mn " << mn << "\n";
for (int i = 0; i < C2; i++) {
// cout << i << " " << leaf[i] << " " << sz2[i] << "\n";
if (leaf[i]) {
mn = min(mn, sz2[i]);
}
}
// cout << "mn " << mn << "\n";
for (int i = 0; i < n; i++) {
// cout << i << " compcomp " << leaf[comp[comp0[i]]] << " " << sz2[comp[comp0[i]]] << "\n";
if (leaf[comp[comp0[i]]] && sz2[comp[comp0[i]]] == mn) {
ans[i] = 1;
}
}
return ans;
}
