#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> adj[5050], INV[5050];
int n, m, a[5050], col[5050], ans[5050], deg[5050];
int solve(){
fill(ans+1, ans+n+1, 2);
queue<int> q;
for (int i=1;i<=n;i++) deg[i] = adj[i].size();
for (int i=1;i<=n;i++) if (col[i]){
ans[i] = 1;
q.push(i);
}
while(!q.empty()){
int s = q.front(); q.pop();
for (auto &v:INV[s]) if (ans[v]==2){
if (a[v]==1){
ans[v] = 1;
q.push(v);
}
else{
deg[v]--;
if (!deg[v]){
ans[v] = 1;
q.push(v);
}
}
}
}
for (int i=1;i<=n;i++) if (ans[i]==2){
q.push(i);
}
for (int i=1;i<=n;i++) if (a[i]==1 && ans[i]==1){
for (auto &v:adj[i]) if (i==v){
if (col[i]==0) deg[i]--;
else deg[i] = 1e9;
}
}
while(!q.empty()){
int s = q.front(); q.pop();
for (auto &v:INV[s]) if (ans[v]==1){
if (a[v]==1){
deg[v]--;
if (!deg[v]){
ans[v] = 2;
q.push(v);
}
}
else{
ans[v] = 2;
q.push(v);
}
}
}
int ret = 0;
for (int i=1;i<=n;i++) if (col[i]==1 && ans[i]==2){
ret = 1;
col[i] = 0;
}
return ret;
}
std::vector<int> who_wins(std::vector<int> A, std::vector<int> R, std::vector<int> U, std::vector<int> V) {
n = A.size();
m = U.size();
for (int i=1;i<=n;i++) a[i] = A[i-1]?1:2;
for (int i=1;i<=n;i++) col[i] = R[i-1];
for (int i=0;i<m;i++){
adj[U[i]+1].push_back(V[i]+1);
INV[V[i]+1].push_back(U[i]+1);
}
while(solve());
vector<int> rans;
for (int i=1;i<=n;i++) rans.push_back((ans[i]==1)?1:0);
return rans;
}
