#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
const int inf=1000000100;
const int MAXN=5010;
int n, m, k;
int Q[MAXN], L, R;
bool dead[MAXN], mark[MAXN];
int deg[MAXN];
vector<int> G[MAXN], GR[MAXN];
vector<int> who_wins(vector<int> typ, vector<int> good, vector<int> U, vector<int> V){
n=typ.size();
m=U.size();
vector<int> ans(n, 1);
for (int i=0; i<m; i++){
G[U[i]].pb(V[i]);
GR[V[i]].pb(U[i]);
}
int sz=n;
while (sz){
memset(mark, 0, sizeof(mark));
L=R=0;
// debug("check1")
for (int i=0; i<n; i++) if (!dead[i]){
if (good[i]) Q[R++]=i;
else{
deg[i]=0;
for (int j:G[i]) deg[i]+=(!dead[j]);
}
}
// debug("check2")
while (L<R){
int v=Q[L++];
mark[v]=1;
for (int u:GR[v]) if (!dead[u] && !mark[u]){
deg[u]--;
if (typ[u] || !deg[u]) Q[R++]=u;
}
}
if (R==sz) break ;
// debug("check3")
L=R=0;
for (int i=0; i<n; i++) if (!dead[i]){
if (!mark[i]) Q[R++]=i;
else{
deg[i]=0;
for (int j:G[i]) deg[i]+=(!dead[j]);
}
}
while (L<R){
int v=Q[L++];
sz--;
ans[v]=0;
dead[v]=1;
for (int u:GR[v]) if (!dead[u] && ans[u]){
deg[u]--;
if (!typ[u] || !deg[u]) Q[R++]=u;
}
}
}
return ans;
}
