#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
vector<vector<pii> > g;
vector<vector<int> > dg, revdg;
vector<bool> vis;
vector<int> order;
vector<int> root, comp_sz;
int cur_comp;
void order_dfs(int v) {
if(vis[v]) {
return;
}
vis[v] = true;
for(int to : dg[v]) {
if(!vis[to])
order_dfs(to);
}
order.push_back(v);
}
void comp_dfs(int v) {
if(vis[v]) {
return;
}
vis[v] = true;
root[v] = cur_comp;
comp_sz[cur_comp] += 1;
for(int to : revdg[v]) {
if(!vis[to]) {
comp_dfs(to);
}
}
}
vector<signed> find_reachable(vector<signed> r, vector<signed> u, vector<signed> v, vector<signed> c) {
int n = r.size();
int m = u.size();
g.assign(n, vector<pii>());
dg.assign(n, vector<int>());
revdg.assign(n, vector<int>());
for(int i = 0; i < m; ++i) {
g[u[i]].push_back({v[i], c[i]});
g[v[i]].push_back({u[i], c[i]});
}
for(int i = 0; i < n; ++i) {
for(auto [to, key] : g[i]) {
if(key == r[i]) {
dg[i].push_back(to);
revdg[to].push_back(i);
}
}
}
vis.assign(n, false);
for(int i = 0; i < n; ++i) {
if(!vis[i]) {
order_dfs(i);
}
}
reverse(order.begin(), order.end());
vis.assign(n, false);
root.assign(n, -1);
for(int x : order) {
// cout << x << ' ';
if(!vis[x]) {
// cout << x << ' ';
comp_sz.push_back(0);
comp_dfs(x);
cur_comp++;
}
}
vector<int> outdeg(n);
for(int i = 0; i < n; ++i) {
assert(root[i] != -1);
for(int to : dg[i]) {
assert(root[to] != -1);
if(root[to] != root[i]) {
outdeg[root[i]]++;
}
}
}
vector<int> ans(n);
for(int i = 0; i < n; ++i) {
if(outdeg[root[i]] == 0) {
ans[i] = 1;
}
}
return ans;
}
/*
7 10
0 1 1 2 2 1 2
0 1 0
0 2 0
1 2 1
1 3 0
2 3 0
3 4 1
3 5 2
4 5 0
4 6 2
5 6 1
4 5
0 1 1 2
0 1 0
0 2 0
1 2 1
1 3 0
1 3 2
*/
