#include "train.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()
const int maxn=5000;
vector<vi> graph(maxn);
vi a,r;
vi depth(maxn,-1);
vi dp(maxn,0);
void dfs(int cur, int d=0, int lst=-1) {
depth[cur]=d;
if (r[cur]) {
lst=d;
}
bool all=1,any=0;
for (auto to:graph[cur]) {
if (depth[to]==-1) {
dfs(to,d+1,lst);
all&=dp[to];
any|=dp[to];
}
else {
all&=(lst>=depth[to]);
any|=(lst>=depth[to]);
}
}
if (a[cur]) {
dp[cur]=any;
}
else {
dp[cur]=all;
}
}
vi who_wins(vi _a, vi _r, vi u, vi v) {
a=_a;
r=_r;
int n=a.size();
int m=u.size();
for (int i=0; i<m; i++) {
graph[u[i]].pb(v[i]);
}
vi win(n,0);
for (int i=0; i<n; i++) {
fill(all(dp),0);
fill(all(depth),-1);
dfs(i);
win[i]=dp[i];
}
return win;
}
