#include "train.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int n, m;
vector<vector<int>> graph, graphr;
vector<bool> active;
vector<int> A;
template<int P>
vector<bool> reachable_from(vector<int> S){
vector<bool> bl(n, 0);
vector<int> cnt(n, 0);
for(int i = 0; i < n; i++) if(active[i]) for(int x: graph[i]) cnt[i]+=active[x];
function<void(int)> dfs = [&](int nd){
if(!active[nd]) return;
if(A[nd] != P){
cnt[nd]--;
if(cnt[nd] > 0) return;
}
if(bl[nd]) return;
bl[nd] = 1;
for(int x: graphr[nd]) dfs(x);
};
for(int x: S){
cnt[x] = 0;
dfs(x);
}
return bl;
}
vector<int> who_wins(vector<int> _A, vector<int> R, vector<int> U, vector<int> V){
swap(A, _A);
n = A.size(), m = U.size();
graph.resize(n), graphr.resize(n);
active.assign(n, 1);
for(int i = 0; i < m; i++) graph[U[i]].pb(V[i]), graphr[V[i]].pb(U[i]);
vector<int> ans(n, 1);
while(1){
vector<int> S;
for(int i = 0; i < n; i++) if(active[i] && R[i]) S.pb(i);
auto bl = reachable_from<1>(S);
S.clear();
for(int i = 0; i < n; i++) if(active[i] && !bl[i]) S.pb(i);
if(S.empty()) break;
bl = reachable_from<0>(S);
for(int i = 0; i < n; i++) if(bl[i]) active[i] = 0, ans[i] = 0;
}
return ans;
}
