#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
int n,m,ch[5005],is[2],V[5005][5005];
vector<int>G[5005],T;
void f(vector<int> &a)
{
while(1)
{
T.clear();
for(int i=0;i<n;i++)
{
if(!ch[i])
{
is[0]=is[1]=0;
for(auto &k:G[i])
{
if(ch[k])
{
V[i][k]=1;
is[1]=1;
}
else is[0]=1;
}
if((a[i] && is[1]) || (!a[i] && !is[0]))T.push_back(i);
}
}
if(!sz(T))break;
for(auto &k:T)ch[k]=1;
}
}
void g(vector<int> &a)
{
while(1)
{
T.clear();
for(int i=0;i<n;i++)
{
if(ch[i])
{
is[0]=is[1]=0;
for(auto &k:G[i])
{
if(!ch[k])is[0]=1;
else
{
if(V[i][i] || V[i][k])is[1]=1;
}
}
if((a[i] && !is[1]) || (!a[i] && is[0]))T.push_back(i);
}
}
if(!sz(T))break;
for(auto &k:T)ch[k]=0;
}
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
n=sz(a);m=sz(u);
vector<int> res(n);
for(int i=0;i<m;i++)G[u[i]].push_back(v[i]);
for(int i=0;i<n;i++)
{
ch[i]=r[i];
if(ch[i])V[i][i]=1;
}
f(a);
g(a);
for(int i=0;i<n;i++)res[i]=ch[i];
return res;
}
