#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5000;
vector<ll> g[N];
bool o[N];
bool x[N];
bool vis[N]={};
bool dfs(ll curr){
// cout<<curr<<endl;
if(vis[curr]) return x[curr];
vis[curr]=1;
vector<pair<bool,ll>> z;
for(auto nxt:g[curr]){
z.push_back({-vis[nxt],nxt});
}
sort(z.begin(),z.end());
bool ans;
if(o[curr]==1){
x[curr]=0;
for(auto nxt:z){
x[curr]|=dfs(nxt.second);
}
ans=x[curr];
}
else{
ans=1;
for(auto nxt:z){
ans&=dfs(nxt.second);
}
}
return x[curr]=ans;
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
ll n=a.size(), m=u.size();
for(ll i=0; i<n; i++){
o[i]=a[i];
g[i].clear();
}
for(ll i=0; i<m; i++){
g[u[i]].push_back(v[i]);
}
vector<int> ans(n,0);
for(ll i=0; i<n; i++){
// cout<<"---"<<i<<"---"<<endl;
if(!r[i]) continue;
for(ll j=0; j<n; j++){
x[j]=0;
vis[j]=0;
}
x[i]=1;
dfs(i);
for(ll j=0; j<n; j++){
vis[j]=0;
}
vis[i]=1;
for(ll j=0; j<n; j++){
if(!vis[j]) dfs(j);
}
for(ll j=0; j<n; j++){
ans[j]|=x[j];
// cout<<x[j]<<" ";
}
// cout<<endl;
}
return ans;
}
