#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 res;
vi U[MAXN],V[MAXN];
vi stat;
int vis[MAXN];
vi bad;
int outdeg[MAXN];
int A[MAXN];
int N;
queue<int> q;
int done[MAXN];
void dest(int x){
done[x]=1;
q.push(x);
while(SZ(q)){
int t = q.front();q.pop();
res[t]=1;
// cout<<"Remove "<<t<<'\n';
for (auto i : U[t])if(!done[i]){
if (A[i] == 1){
// A owns it then can just remove
q.push(i);
done[i]=1;
}else{
--outdeg[i];
if (outdeg[i] == 0){q.push(i);done[i]=1;}
}
}
}
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
N = SZ(a);
res.resize(N,0);
for (int i=0;i<N;++i)A[i] = a[i];
int m = SZ(u);
for (int i=0;i<m;++i){
V[u[i]].pb(v[i]);
U[v[i]].pb(u[i]);
// cout<<"Appending "<<u[i]<<" to "<<v[i]<<'\n';
++outdeg[u[i]];
}
for (int i=0;i<N;++i)if(r[i])stat.pb(i);
assert(SZ(stat) == 1);
int rt = stat[0];
dest(rt);
// The node needs to be able to directly reach one of the done nodes
if (A[rt]){
for (auto v : V[rt])if(done[v])return res;
}
else{
int ok = 1;
for (auto v : V[rt])if (!done[v])ok = 0;
if (ok)return res;
}
res.resize(N,0);
assert(0);
return res;
}
