#include "train.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
const int mxN = 5005;
int N, M, A[mxN];
vector<int> al[mxN];
int rf[mxN], src;
int f(int u) {
if (~rf[u]) return rf[u];
rf[u] = -2;
if (A[u]) {
bool tmp = 0;
for (int v : al[u]) {
if (v == src) tmp |= 1;
else if (rf[v] != -2) tmp |= f(v);
}
return rf[u] = tmp;
} else {
bool tmp = 1;
for (int v : al[u]) {
if (v == src) tmp &= 1;
else if (rf[v] != -2) tmp &= f(v);
}
return rf[u] = tmp;
}
}
int rg[mxN][mxN];
int g(int u, int p) {
if (~rg[u][p]) return rg[u][p];
if (A[u]) {
rg[u][p] = 0;
for (int v : al[u]) {
rg[u][p] |= g(v,p-1);
}
} else {
rg[u][p] = 1;
for (int v : al[u]) {
rg[u][p] &= g(v,p-1);
}
}
return rg[u][p];
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
N = SZ(a);
FOR(i,0,N-1){
A[i] = a[i];
}
M = SZ(u);
FOR(i,0,M-1){
al[u[i]].push_back(v[i]);
}
memset(rg,-1,sizeof rg);
FOR(i,0,N-1){
if (r[i]) {
src = i;
memset(rf,-1,sizeof rf);
f(src);
FOR(j,0,N-1) if (rf[i] == 1) rg[i][0] = 1;
}
}
FOR(i,0,N-1){
if (rg[i][0] == 1) {
FOR(p,0,N-1) rg[i][p] = 1;
} else {
rg[i][0] = 0;
}
}
vector<int> res(N);
for (int i = 0; i < N; i++) {
res[i] = g(i,N);
}
return res;
}
