#include <bits/stdc++.h>
#include "train.h"
//#include "grader.cpp"
using namespace std ;
const int MAX = 5010 ;
int A[MAX] , R[MAX] ;
vector< vector<int> >adj(MAX) ;
int n ;
int vis[MAX] , mark[MAX] , prv[MAX] ;
bool dfs(int node)
{
vis[node] = 1 , mark[node] = 1 ;
for(auto &child : adj[node])
{
if(vis[child])
{
if(mark[child])
{
int a = node ;
bool flag = 0 ;
while(a != child)
{
flag |= R[a] ;
a = prv[a] ;
}
flag |= R[a] ;
if(flag == A[node])
{
mark[node] = 0 ;
return 1 ;
}
}
continue ;
}
prv[child] = node ;
bool t = dfs(child) ;
if(A[node] && A[child] == t)
{
mark[node] = 0 ;
return 1 ;
}
else if(!A[node] && A[child] != t)
{
mark[node] = 0 ;
return 1 ;
}
}
mark[node] = 0 ;
return 0 ;
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
n = a.size() ;
int m = u.size() ;
for(int i = 1 ; i <= n ; ++i)
{
A[i] = a[i-1] ;
R[i] = r[i-1] ;
}
for(int i = 0 ; i < m ; ++i)
adj[u[i] + 1].push_back(v[i] + 1) ;
vector<int>ans ;
for(int i = 1 ; i <= n ; ++i)
{
memset(vis , 0 , sizeof(vis)) ;
bool t = dfs(i) ;
if(A[i] == t)
ans.push_back(1) ;
else
ans.push_back(0) ;
}
return ans ;
}
