#include "train.h"
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> g;
vector<int> r, w;
bool find_cycle(int s){
vector<bool> seen(n, false);
queue<int> q;
q.push(s);
while (!q.empty()){
int cur = q.front();
q.pop();
if (seen[cur] || r[cur]) continue;
seen[cur] = true;
for (int next : g[cur]){
if (next == s) return true;
q.push(next);
}
}
return false;
}
bool win(int s){
vector<bool> seen(n, false);
queue<int> q;
q.push(s);
while (!q.empty()){
int cur = q.front();
q.pop();
if (seen[cur]) continue;
seen[cur] = true;
for (int next : g[cur]){
if (w[next]) return true;
q.push(next);
}
}
return false;
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v){
n = a.size();
m = u.size();
::r = r;
vector<int> res(n);
g.resize(n);
for (int i=0; i<m; i++) g[u[i]].push_back(v[i]);
w.resize(n, false);
for (int i = 0; i<n; i++){
if (!r[i]) w[i] = find_cycle(i);
}
for (int i=0; i<n; i++) res[i] = win(i);
return res;
}
