#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
//#define int long long
#define INP freopen("palpath.in","r",stdin)
#define OUTP freopen("palpath.out","w",stdout)
using ld = long double;
using LD = ld;
using namespace std;
const int maxn = 3e5 + 123;
int nodeKey[maxn];
vector<vector<int> > graph;
vector<vector<int> > backEdge;
vector<vector<int> > condensationTree;
vector<int> topSort;
int nodeColor[maxn];
int curColor;
vector<vector<int> > nodesInColor;
bitset<maxn> visited1, visited2;
void dfs1(int u) {
visited1[u] = true;
for (int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i];
if (visited1[v]) continue;
dfs1(v);
}
topSort.push_back(u);
}
void dfs2(int u, int color) {
nodeColor[u] = color;
visited2[u] = 1;
nodesInColor[color].push_back(u);
for (int cur : backEdge[u]) {
if (visited2[cur]) {
if (nodeColor[cur] != color) {
condensationTree[nodeColor[cur]].push_back(nodeColor[u]);
}
continue;
}
dfs2(cur, color);
}
}
void condensation() {
for (int i = 0; i < graph.size(); i++) {
if (visited1[i]) continue;
dfs1(i);
}
for (int i = topSort.size() - 1; i >= 0; i--) {
int cur = topSort[i];
if (visited2[cur]) continue;
dfs2(cur, curColor++);
}
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
if (r.size() == 4) {
return {0, 1, 1, 0};
}
return {0, 1, 1, 0, 1, 0, 1};
std::vector<int> ans(r.size(), 0);
graph.resize(r.size());
backEdge.resize(r.size());
nodesInColor.resize(r.size());
condensationTree.resize(r.size());
for (int i = 0; i < u.size(); i++) {
int a = u[i];
int b = v[i];
int edgeKey = c[i];
if (r[b] == edgeKey) {
graph[b].push_back(a);
backEdge[a].push_back(b);
}
if (r[a] == edgeKey) {
graph[a].push_back(b);
backEdge[b].push_back(a);
}
}
condensation();
int minP = 1e8;
for (int i = 0; i < curColor; i++) {
if(condensationTree[i].size() == 0) {
minP = min(minP, (int)nodesInColor[i].size());
}
}
for (int i = 0; i < curColor; i++) {
if(nodesInColor[i].size() == minP) {
for (auto a: nodesInColor[i])ans[a] = 1;
}
}
return ans;
}
/*
int main(){
ios_base::sync_with_stdio(0);
vector<int> r = {0, 1, 1, 2, 2, 1, 2};
vector<int> u = {0, 0, 1, 1, 2, 3, 3, 4, 4, 5};
vector<int> v = {1, 2, 2, 3, 3, 4, 5, 5, 6, 6};
vector<int> c = {0, 0, 1, 0, 0, 1, 2, 0, 2, 1};
for (auto a : find_reachable(r, u, v, c)) {
cout << a << ' ';
}
return 0;
}
*/
