#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
#define pb push_back
const int N=5050;
vector<int> R[N];
int deg[N],in[N];
bool was[N],vis[N],A[N];
void AddEdge(int u, int v){ R[v].pb(u);deg[u]++;}
void DelNode(int u){ for(int i=0;i<R[u].size();i++) deg[R[u][i]]--;was[u]=1;}
void init(int n){ for(int i=1;i<=n;i++) vis[i]=0;}
queue<int> q;
vector<int> st;
void BFS(int n, bool mod)
{
init(n);
int i;
for(i=1;i<=n;i++) if(!was[i]) in[i]=(A[i]==mod)?1:deg[i];
for(i=0;i<st.size();i++) vis[st[i]]=1,q.push(st[i]);
while(q.size())
{
int u=q.front();
q.pop();
for(i=0;i<R[u].size();i++)
{
int v=R[u][i];
if(vis[v] || was[v]) continue;
in[v]--;
if(!in[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
vector<int> ch;
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
int n=a.size(),i,m=v.size();
for(i=0;i<n;i++) A[i+1]=a[i];
for(i=0;i<n;i++) if(r[i]) ch.pb(i+1);
for(i=0;i<m;i++) AddEdge(u[i]+1,v[i]+1);
bool done;
do
{
st.clear();
for(i=0;i<ch.size();i++) if(!was[ch[i]]) st.pb(ch[i]);
BFS(n,1);
st.clear();
for(i=1;i<=n;i++) if(!was[i] && !vis[i]) st.pb(i);
BFS(n,0);
done=0;
for(i=1;i<=n;i++) if(!was[i] && vis[i]) done=1,DelNode(i);
}while(done);
vector<int> ans;
for(i=1;i<=n;i++) ans.pb(!was[i]);
return ans;
}
/*int main()
{
int n,m,i,x,y;
vector<int> a,r,u,v;
scanf("%i %i",&n,&m);
for(i=0;i<n;i++) scanf("%i",&x),a.pb(x);
for(i=0;i<n;i++) scanf("%i",&x),r.pb(x);
for(i=0;i<m;i++) scanf("%i %i",&x,&y),u.pb(x),v.pb(y);
vector<int> ans=who_wins(a,r,u,v);
for(i=0;i<ans.size();i++) printf("%i ",ans[i]);printf("\n");
return 0;
}*/
