#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int>pii;
int n,m,R[5005],A[5005],go[5005],self[5005],C[5005],ch[5005];
vector<int>G[5005],rev[5005],SCC[5005],SCCX[5005],E[5005];
int v[5005],st[5005],ind[5005],sz,col,D[5005];
void dfs1(int p)
{
v[p]=1;
for(auto &k:G[p])
{
if(!v[k])dfs1(k);
}
st[sz++]=p;
}
void dfs2(int p)
{
v[p]=1;
SCC[sz].push_back(p);
go[p]=sz;
for(auto &k:rev[p])
{
if(!v[k])dfs2(k);
}
}
void dfsx1(int p)
{
v[p]=1;
for(auto &k:G[p])
{
if(!R[k] && !v[k])dfsx1(k);
}
st[sz++]=p;
}
void dfsx2(int p)
{
v[p]=1;
SCCX[sz].push_back(p);
for(auto &k:rev[p])
{
if(!R[k] && !v[k])dfsx2(k);
}
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> uu, vector<int> vv) {
n=sz(a);
m=sz(uu);
vector<int> res(n);
for(int i=0;i<n;i++)
{
A[i]=a[i];
R[i]=r[i];
}
for(int i=0;i<m;i++)
{
if(uu[i]==vv[i])
{
self[uu[i]]=1;
continue;
}
G[uu[i]].push_back(vv[i]);
rev[vv[i]].push_back(uu[i]);
}
sz=0;
memset(v,0,sizeof(v));
for(int i=0;i<n;i++)
{
if(!R[i] && !v[i])dfsx1(i);
}
memset(v,0,sizeof(v));
int o=sz;
sz=0;
for(int i=o-1;i>=0;i--)
{
if(!v[st[i]])
{
sz++;
dfsx2(st[i]);
}
}
for(int i=1;i<=sz;i++)
{
if(sz(SCCX[i])==1)
{
if(self[SCCX[i][0]]==1)ch[SCCX[i][0]]=1;
continue;
}
for(auto &k:SCCX[i])
{
ch[k]=1;
}
}
sz=0;
memset(v,0,sizeof(v));
for(int i=0;i<n;i++)if(!v[i])dfs1(i);
memset(v,0,sizeof(v));
sz=0;
for(int i=n-1;i>=0;i--)
{
if(!v[st[i]])
{
sz++;
dfs2(st[i]);
}
}
for(int i=1;i<=sz;i++)
{
for(auto &k:SCC[i])
{
if(ch[k])C[i]=1;
}
}
for(int i=0;i<m;i++)
{
if(go[uu[i]]!=go[vv[i]])
{
E[go[uu[i]]].push_back(go[vv[i]]);
ind[go[vv[i]]]++;
}
}
queue<int>P;
for(int i=1;i<=sz;i++)
{
if(ind[i]==0)P.push(i);
}
vector<int>dag;
while(!P.empty())
{
int p=P.front();P.pop();
dag.push_back(p);
for(auto &k:E[p])
{
ind[k]--;
if(ind[k]==0)P.push(k);
}
}
for(int i=sz(dag)-1;i>=0;i--)
{
if(C[dag[i]]==1)D[dag[i]]=1;
else
{
for(auto &k:E[dag[i]])
{
if(D[k]==1)D[dag[i]]=1;
}
}
}
for(int i=0;i<n;i++)
{
res[i]=1-D[go[i]];
}
return res;
}
