#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;
ll n;
ll A[MAXN];
ll R[MAXN];
bool vis[MAXN];
bool arezou[MAXN];
vector<ll> radj[MAXN];
vector<ll> adj[MAXN];
ll res[MAXN];
ll dfs(ll nd, ll ini){
if(vis[nd] && nd == ini) return 1;
if(vis[nd]) return 0;
vis[nd]=true;
debug(">>>>>>>>>>> "<<nd<<'\n');
res[nd]=(A[nd]+1)%2;
for(auto i:adj[nd]){
if(A[nd]) res[nd]=max(res[nd],dfs(i,ini));
else res[nd]=min(res[nd],dfs(i,ini));
}
debug("<<<<< "<<nd<<'\n');
return res[nd];
}
vector<int> ress;
void expand(){
ll cnt[MAXN];
forn(i,0,n){
if(!A[i]) cnt[i]=SZ(adj[i]);
else cnt[i]=1;
}
forn(i,0,n){
debug("mycnt "<<cnt[i]<<" "<<A[i]<<'\n');
}
priority_queue<pair<ll,ll>> pq;
forn(i,0,n){
if(arezou[i]){
pq.push({0,i});
cnt[i]=0;
}
}
while(!pq.empty()){
ll nd = pq.top().snd;
ll c = pq.top().fst;
pq.pop();
debug(" expand "<<nd<<" "<<c<<'\n');
if(vis[nd]) continue;
vis[nd]=true;
if(c>=0){
arezou[nd]=true;
}else{
arezou[nd]=false;
}
for(auto j:radj[nd]){
if(arezou[nd]){
cnt[j]--;
}
debug(" Metemos "<<-cnt[j]<<" "<<j<<'\n');
pq.push({-cnt[j],j});
}
}
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
n=SZ(r);
forn(i,0,SZ(a)) A[i]=a[i];
forn(i,0,SZ(r)) R[i]=r[i];
forn(i,0,SZ(u)){
radj[v[i]].pb(u[i]);
adj[u[i]].pb(v[i]);
}
forn(i,0,SZ(r)){
if(r[i]){
res[i]=(A[i]+1)%2;
for(auto j:adj[i]){
mset(vis,false);
debug("Probando en "<<i<<" "<<j<<'\n');
vis[i]=true;
if(A[i]) res[i]=max(res[i],dfs(j,i));
else res[i]=min(res[i],dfs(j,i));
}
if(res[i]){
arezou[i]=true;
}else{
arezou[i]=false;
}
}
}
mset(vis,false);
expand();
forn(i,0,SZ(r)){
debug(i<<" "<<(arezou[i]?"Arezou":"Borzou")<<'\n');
ress.pb(arezou[i]?1:0);
}
return ress;
}
