#include "train.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define pb emplace_back
#define mp make_pair
#define MAXN 5010
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
vi V[MAXN], U[MAXN];
vi safe;
int a=1,b=1,N;
int curstack[MAXN];
int A[MAXN];
stack<int> stk;
vi res;
int vis[MAXN];
int dfs(int x){
int out=0;
for (auto i : V[x]){
if (safe[i])return safe[x] = 1;
if (vis[i]){
// Cylce exists
out=1;
continue;
}
vis[i]=1;
int t = dfs(i);
if (t)out=1;
}
if (out)safe[x] = 1;
return out;
}
int dfs2(int x){
int out=0;
for (auto i : V[x])if (!vis[i]){
if (safe[i])return 1;
vis[i]=1;
out=max(out,dfs2(i));
}
return out;
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
N = SZ(a);
safe.resize(N,0);
for (int i=0;i<N;++i)A[i] = a[i];
for (int i=0;i<N;++i)assert(a[i]==0);
int M = SZ(u);
for (int i=0;i<M;++i){
if (r[u[i]] || r[v[i]])continue;
V[u[i]].pb(v[i]);
}
for (int i=0;i<N;++i){
memset(vis,0,sizeof(vis));
vis[i]=1;
dfs(i);
}
// for (int i=0;i<N;++i)cout<<safe[i]<<' ';cout<<'\n';
for (int i=0;i<N;++i)V[i].clear();
for (int i=0;i<M;++i){
V[u[i]].pb(v[i]);
}
for (int i=0;i<N;++i)if(safe[i] == 0){memset(vis,0,sizeof(vis));vis[i]=1;safe[i] = dfs2(i);}
return safe;
}
