#include "train.h"
#include <bits/stdc++.h>
using namespace std;
#define maxn 5005
typedef vector<int> vi;
bool vis[maxn],cycle[maxn];
int good[maxn];
vi AL[maxn],a,r,u,v;
bool dfs(int u,int rt){
vis[u]=true;
bool have=false,all=true;
for(int v:AL[u]){
if(v==rt){
have=true;
continue;
}
if(!vis[v])dfs(v,rt);
else if(!cycle[v])all=false;
else have=true;
}
if(a[u]==1&&have)cycle[u]=true;
else if(a[u]==0&&all)cycle[u]=true;
return cycle[u];
}
bool dfs2(int u,int rt){
vis[u]=true;
bool have=false,all=true;
for(int v:AL[u]){
if(v==rt){
have=true;
continue;
}
if(!vis[v])dfs2(v,rt);
if(!cycle[v])all=false;
else have=true;
}
if(r[u]!=1&&a[u]==1&&all)cycle[u]=true;
else if(r[u]!=1&&a[u]==0&&have)cycle[u]=true;
return cycle[u];
}
vi who_wins(vi _a,vi _r,vi _u,vi _v){
a=_a,r=_r,u=_u,v=_v;
int n=a.size(),m=u.size();
for(int i=0;i<m;++i){
AL[u[i]].push_back(v[i]);
}
memset(good,-1,sizeof good);
for(int i=0;i<n;++i){
for(int j=0;j<n;++j)vis[j]=cycle[j]=false;
if(r[i]==1&&dfs(i,i))good[i]=1;
else if(r[i]==0&&dfs2(i,i))good[i]=0;
}
for(int i=0;i<n;++i){
bool take=false;
for(int u=0;u<n;++u){
if(good[u]!=-1)continue;
bool have=false,all=true;
for(int v:AL[u]){
if(good[v]==1)have=true;
else if(good[v]==0)all=false;
}
if(a[u]==1)good[u]=have;
else good[u]=all;
take=true;
}
if(!take)continue;
}
vi ans(n,0);
for(int i=0;i<n;++i)ans[i]=good[i];
return ans;
}
