#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
const int MAXN=5e3+10;
const ll inf=1e16;
typedef pair<int,int> pii;
int n,m;
vector<int> g[MAXN],charged,mark;
bool z[MAXN];
stack<int> st;
bool dfs(int x){
z[x]=1;
st.push(x);
bool win=0;
for(auto u:g[x]){
if(!z[u]){
bool ok=dfs(u);
if(mark[u]!=mark[x]) ok^=1;
win|=ok;
continue;
}
bool ok=0;
vector<int> ad;
while(!st.empty()){
auto a=st.top(); st.pop(); ad.pb(a);
ok|=charged[a];
if(a==u) break;
}
reverse(all(ad));
for(auto a:ad) st.push(a);
if(!mark[x]) ok^=1;
win|=ok;
}
st.pop();
z[x]=0;
return win;
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
n=sz(a),m=sz(u);
charged=r;
fall(i,0,m-1) g[u[i]].pb(v[i]);
mark=a;
vector<int> ans(n);
fall(i,0,n-1){
ans[i]=dfs(i);
if(!mark[i]) ans[i]^=1;
}
return ans;
}
