#include "train.h"
#include <iostream>
#include <vector>
using namespace std;
int DFS_wins(int u, vector<vector<int> > & G, vector<int> & wins, vector<int> & a){
if (wins[u] != -1) return wins[u];
wins[u] = 0;
int res = a[u] ^ 1;
for (int v : G[u]){
if (a[u]){
res |= DFS_wins(v, G, wins, a);
} else {
res &= DFS_wins(v, G, wins, a);
}
}
/* cout << u << ":\n";
for (int v : G[u]){
cout << v << ' ' << wins[v] << ", ";
}
cout << '\n' << res << '\n'; */
wins[u] = res;
return res;
}
void DFS_reverse(int u, bool bat, vector<vector<int> > & G, vector<int> & wins, vector<int> & a, vector<int> & inEdges){
if (wins[u] != -1) return;
if (a[u] == 1 || bat){
wins[u] = 1;
} else {
inEdges[u]--;
if (inEdges[u] == 0){
wins[u] = 1;
} else {
return;
}
}
for (int v : G[u]){
DFS_reverse(v, false, G, wins, a, inEdges);
}
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v){
int N = a.size(), M = u.size(); // 1 -> the battery person has it
vector<vector<int> > G(N), F(N);
vector<int> inEdgesF(N, 0);
for (int i=0; i<M; ++i){
G[u[i]].push_back(v[i]);
F[v[i]].push_back(u[i]);
inEdgesF[u[i]]++;
}
vector<int> wins(N, -1); // -1 idk, 0 no, 1 yea; // win = battery ()
for (int i=0; i<N; ++i) {
if (r[i] == 1) {
DFS_reverse(i, true, F, wins, a, inEdgesF);
}
}
for (int i=0; i<N; ++i){
wins[i] = DFS_wins(i, G, wins, a);
}
return wins;
}
/*
int main(){
int N, M; cin >> N >> M;
vector<int> a(N), r(N), u(M), v(M);
for (int & x : a) cin >> x;
for (int & x : r) cin >> x;
for (int i=0; i<M; ++i){
cin >> u[i] >> v[i];
}
vector<int> w = who_wins(a,r,u,v);
for (int n : w) cout << n << ' ';
cout << '\n';
}
4 9
1 0 1 0
0 1 0 0
0 1
0 0
0 2
2 1
1 2
2 3
3 1
3 0
1 3
---
1 1 1 0
*/
