#include <bits/stdc++.h>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
#define N_ 5010
int n, m, removed[N_], attr[N_], Q[N_], Deg[N_];
vi E[N_], F[N_];
auto Attr(vi T, int ck, vi &a, vi &r, vi &vis){
int head=0,tail=0;
rep(i,n)vis[i]=Deg[i]=0;
auto QAdd = [&](int x){
if(!removed[x] && !vis[x])Q[++tail] = x, vis[x]=1;
};
rep(i,n){
if(removed[i])continue;
if(T[i]){
QAdd(i);
}
for(auto &x: F[i]){
if(removed[x])continue;
if(a[x] != ck)Deg[x]++;
}
}
rep(i,n){
if(removed[i])continue;
if(a[i] != ck && !Deg[i])QAdd(i);
}
while(head < tail){
int x = Q[++head];
for(auto &y : F[x]){
if(removed[y])continue;
if(a[y] == ck)QAdd(y);
if(a[y] != ck){
Deg[y]--;
if(!Deg[y])QAdd(y);
}
}
}
}
extern std::vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
n = a.size();
m = u.size();
int i, j, k;
vi res(n), T(n);
rep(i,m){
E[u[i]].pb(v[i]);
F[v[i]].pb(u[i]);
}
vi Attr0(n), Attr1(n);
while(1){
rep(i,n){
T[i]=0;
if(removed[i])continue;
if(r[i])T[i]=1;
}
Attr(T, 1, a, r, Attr1);
rep(i,n)if(!removed[i]) Attr1[i] = !Attr1[i];
Attr(Attr1, 0, a, r, Attr0);
int ck=0;
rep(i,n){
if(!removed[i] && Attr0[i])removed[i]=1, ck=1;
}
if(!ck)break;
}
rep(i,n)res[i] = !removed[i];
return res;
}
