#include<bits/stdc++.h>
#include "train.h"
using namespace std;
const int nax = 5000;
int n, m;
vector<int>g[nax];
vector<int>A, R;
vector<int>cr(nax, -1);
vector<int>stk;
bool solve(int v) {
cr[v] = stk.size();
stk.push_back(v);
bool win = false;
for(int u : g[v]) {
if(cr[u]==-1) {
win |= solve(u) ^ (A[v]!=A[u]);
} else {
bool is = false;
for(int j=stk.size()-1; j>=cr[u]; --j) {
is |= R[stk[j]];
}
if(is && A[v]) win = true;
else if(!is && !A[v]) win = true;
}
}
cr[v] = -1;
stk.pop_back();
return win;
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
n = a.size(), m = u.size();
for(int i=0; i<m; ++i) {
g[u[i]].push_back(v[i]);
}
A = a, R = r;
vector<int>res(n);
for(int i=0; i<n; ++i) {
res[i] = solve(i) ^ (A[i]!=1);
}
return res;
}
