#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(a) (int)(a.size())
const int MAXN = 5555;
vector<int>g[MAXN],gr[MAXN];
std::vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
int n = sz(a);
vector<int>win(n,0);
for(int i=0;i<sz(u);i++){
g[u[i]].push_back(v[i]);
gr[v[i]].push_back(u[i]);
}
for(int i=0;i<n;i++){
if(!r[i])continue;
vector<bool>path(n,0);
vector<int>cnt(n,0);
for(int j=0;j<n;j++){
if(!a[j])cnt[j] = sz(g[j]);
}
queue<int>q;
q.push(i);
path[i] = 1;
while(!q.empty()){
int v = q.front();
q.pop();
for(int x:gr[v]){
if(path[x])continue;
if(a[x]){
path[x] = 1;
q.push(x);
}else{
cnt[x]--;
if(!cnt[x]){
path[x] = 1;
q.push(x);
}
}
}
}
//path(x) = x can be forced to go to i
bool cyc = 0;
int c = 0;
for(int x:g[i]){
if(path[x] && a[i])cyc = 1;
if(path[x] && !a[i])c++;
}
if(c == sz(g[i]))cyc = 1;
if(cyc){
for(int j=0;j<n;j++){
if(path[j])win[j] = 1;
}
}
}
vector<int>cnt(n,0);
queue<int>q;
for(int i=0;i<n;i++){
cnt[i] = sz(g[i]);
if(win[i])q.push(i);
}
while(!q.empty()){
int v = q.front();
q.pop();
for(int x:gr[v]){
if(win[x])continue;
if(a[x]){
win[x] = 1;
q.push(x);
}else{
cnt[x]--;
if(!cnt[x]){
win[x] = 1;
q.push(x);
}
}
}
}
return win;
}
