#include <bits/stdc++.h>
#define MAX 5010
using namespace std;
int N, M;
int curComponent;
int node[MAX];
bool marc[MAX][2];
bool isCycle[MAX];
bool isSpecial[MAX];
bool hasRecharge[MAX];
vector<int> order;
vector<int> SCC[MAX];
vector<int> grafo[MAX][2];
void DFS(int i, int type, int& sz)
{
marc[i][type] = true;
sz++;
for(int g = 0 ; g < grafo[i][type].size() ; g++)
{
int prox = grafo[i][type][g];
//printf("i = %d prox = %d %d\n",i,prox,marc[prox][type]);
if(marc[prox][type]) continue;
if(type == 1)
{
node[prox] = node[i];
if( isSpecial[prox] ) hasRecharge[ node[i] ] = true;
}
DFS(prox , type , sz);
}
if(type == 0) order.push_back( i );
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
N = a.size(); M = u.size();
for(int g = 0 ; g < M ; g++)
{
grafo[ u[g] + 1 ][0].push_back( v[g] + 1 );
grafo[ v[g] + 1 ][1].push_back( u[g] + 1 );
if(u[g] == v[g]) isCycle[ u[g] + 1 ] = true;
//printf("OIII %d %d\n",u[g] + 1,v[g] + 1);
}
for(int g = 0 ; g < N ; g++)
{
if(r[g] == 1) isSpecial[g + 1] = true;
else isSpecial[g + 1] = false;
}
int t = 0;
for(int g = 1 ; g <= N ; g++)
if(!marc[g][0]) DFS(g , 0 , t);
while(!order.empty())
{
int cur = order.back();
order.pop_back();
if(marc[cur][1]) continue;
node[cur] = ++curComponent;
if(isCycle[cur] && isSpecial[cur])
hasRecharge[ node[cur] ] = true;
//printf("cuuur = %d\n",cur);
int size = 0;
DFS(cur , 1 , size);
if( isSpecial[cur] && size > 1 ) hasRecharge[ node[cur] ] = true;
//printf("cur = %d %d\n",cur,hasRecharge[node[cur]]);
}
for(int g = 0 ; g < M ; g++)
{
int i = u[g] + 1;
int j = v[g] + 1;
i = node[i]; j = node[j];
if(i == j) continue;
SCC[j].push_back( i );
}
for(int g = curComponent ; g > 0 ; g--)
{
if(!hasRecharge[g]) continue;
for(int h = 0 ; h < SCC[g].size() ; h++)
hasRecharge[ SCC[g][h] ] = true;
}
vector<int> ans;
for(int g = 1 ; g <= N ; g++)
{
int i = node[g];
if(hasRecharge[i]) ans.push_back( 1 );
else ans.push_back( 0 );
}
return ans;
}
/*int main()
{
int nn, mm, n1, n2;
scanf("%d %d",&nn,&mm);
vector<int> v1, v2;
vector<int> uu, vv;
for(int g = 0 ; g < nn ; g++)
v1.push_back( 1 );
v2.push_back(3);
for(int g = 0 ; g < mm ; g++)
{
scanf("%d %d",&n1,&n2);
n1--;n2--;
uu.push_back( n1 );
vv.push_back( n2 );
}
vector<int> ans = who_wins(v1 , v2 , uu , vv);
for(int g = 0 ; g < nn ; g++)
printf("%d ",ans[g]);
}*/
