#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
#include "train.h"
#endif
using namespace std;
const int MAXN = 5000;
bool is_gen[MAXN];
bool vis[MAXN];
bool local_vis[MAXN];
vector<int> adj[MAXN];
int cur_gen=0;
int start=0;
int gen[MAXN];
bool dfs(int v)
{
if(is_gen[v]) cur_gen++;
gen[v]=cur_gen;
vis[v]=1;
local_vis[v]=1;
for(auto u:adj[v])
{
if(local_vis[u] && cur_gen>0 && (gen[v]!=gen[u] || is_gen[u]==1)) return 1;
if(vis[u]) continue;
bool cur=dfs(u);
if(cur) return 1;
}
if(is_gen[v]) cur_gen--;
local_vis[v]=0;
return 0;
}
vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V)
{
int n = A.size();
int m = U.size();
for(int i=0; i<n; i++) is_gen[i]=R[i];
for(int i=0; i<m; i++)
{
adj[U[i]].push_back(V[i]);
}
vector<int> ans;
for(int i=0; i<n; i++)
{
cur_gen=0;
start=i;
for(int i=0; i<n; i++)
{
vis[i]=0;
local_vis[i]=0;
gen[i]=0;
}
ans.push_back(dfs(i));
}
return ans;
}
#ifdef ARTHUR_LOCAL
int main()
{
for(auto e:who_wins({0,1},{0,1},{0,0,1,1},{0,1,0,1}))
{
cout << e << endl;
}
}
#endif
