#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int MX=5010;
vector<int> G[MX], H[MX];
int n;
bool tmp[MX];
vi win, A, R;
const vi& find(const vi &S, bool c){
static bool in[MX]={}; int deg[MX]={};
static vi T; static queue<int> Q;
for(int i=0; i<n; i++) in[i]=false, deg[i]=0;
T.clear();
for(int i=0; i<n; i++) if(win[i]<0)
for(int x:G[i]) deg[i]+=win[x]<0;
for(int x:S) in[x]=true, Q.push(x);
while(!Q.empty()){
int v=Q.front(); Q.pop();
for(int x:H[v]){
if(in[x] || win[x]>=0) continue;
if(A[x]==c) in[x]=true, Q.push(x);
else{
deg[x]--;
if(deg[x]==0) in[x]=true, Q.push(x);
}
}
}
for(int i=0; i<n; i++) if(in[i]) T.push_back(i);
return T;
}
vi who_wins(vi _A, vi _R, vi U, vi V) {
n=_A.size(); win.resize(n, -1);
A=_A, R=_R;
for(int i=0; i<(int)U.size(); i++){
G[U[i]].push_back(V[i]);
H[V[i]].push_back(U[i]);
}
vi S, T, X, Y;
while(true){
S.clear(), X.clear();
for(int i=0; i<n; i++) if(R[i] && win[i]<0) S.push_back(i);
T=find(S, 1);
for(int i=0; i<n; i++) tmp[i]=win[i]>=0;
for(int x:T) tmp[x]=true;
for(int i=0; i<n; i++) if(!tmp[i]) X.push_back(i);
if(X.empty()){
for(int x:T) win[x]=1;
break;
}
else{
Y=find(X, 0);
for(int x:Y) win[x]=0;
}
}
return win;
}
