#include "train.h"
#include <bits/stdc++.h>
#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b;i++)
#define mset(a,v) memset(a,v,sizeof(a))
using namespace std;
typedef long long ll;
const int MAXN = 5000+5;
vector<ll> adj[MAXN];
ll lvl[MAXN];
bool vis[MAXN];
bool good[MAXN];
ll R[MAXN];
vector<pair<ll,ll>> pila;
bool yes=true;
void dfs(ll nd,ll ini,ll cnt){
if(vis[nd] && cnt==0){
yes=true;
//cout<<"YES\n";
}
//cout<<nd<<"-->>>\n";
if(vis[nd]) return;
vis[nd]=true;
for(auto i:adj[nd]) if(!R[i]){
dfs(i,ini,cnt);
}
for(auto i:adj[nd]) if(R[i]){
dfs(i,ini,cnt+1);
}
vis[nd]=false;
//cout<<nd<<"<<<--\n";
}
void ndfs(ll nd, ll p){
vis[nd]=true;
if(good[nd]) yes=true;
if(yes) return;
for(auto i:adj[nd]) if(i!=p && !vis[i]){
ndfs(i,nd);
if(yes) return;
}
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
forn(i,0,SZ(u)){
adj[u[i]].pb(v[i]);
}
forn(i,0,SZ(r)){
R[i]=r[i];
}
mset(good,0);
forn(i,0,SZ(r)) if(!r[i]){
mset(vis,false);
yes=false;
dfs(i,i,0);
//cout<<yes<<" "<<i<<'\n';
if(yes) good[i]=1;
}
vector<int> res(SZ(r),0);
forn(i,0,SZ(r))if(!good[i]){
mset(vis,false);
yes=false;
ndfs(i,-1);
if(yes) res[i]=0;
else res[i]=1;
}
return res;
}
