#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))
#ifdef D
#define debug(x) cout<<" (dbgline) "<< x
#else
#define debug(x) // nada
#endif
using namespace std;
typedef long long ll;
const int MAXN = 5000+5;
vector<ll> adj[MAXN];
ll lvl[MAXN];
bool vis[MAXN];
ll R[MAXN];
ll A[MAXN];
vector<pair<ll,ll>> pila;
ll dfs(ll nd,ll lv){
if(vis[nd]){
ll j=lower_bound(ALL(pila),pair<ll,ll>{lvl[nd],(ll)0})-pila.begin();
ll cnt = pila.back().snd - (j-1>=0?pila[j-1].snd:0);
return (cnt?1:0);
}
vis[nd]=true;
lvl[nd]=lv;
pila.pb({lv,R[nd]+(SZ(pila)>0?pila.back().snd:0)});
ll res = (A[nd]?0:1);
for(auto i:adj[nd]){
if(A[nd]) res=max(res,dfs(i,lv+1));
else res=min(res,dfs(i,lv+1));
}
debug(nd<<" "<<lv<<" "<<res<<'\n');
vis[nd]=false;
pila.pop_back();
return res;
}
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];
}
forn(i,0,SZ(a)) A[i]=a[i];
vector<int> res(SZ(r));
forn(i,0,SZ(r)){
debug("----"<<i<<'\n');
mset(vis,false);
pila.clear();
res[i]=dfs(i,0);
}
return res;
}
