#include "train.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (long long x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<ll,ll> pll;
using namespace std;
const int N = 5050;
vector<int> A[N];
int col[N];
bool charg[N];
int n, m;
bool vis[N];
bool can_reach_self[N];
int win[N];
bool dfs0(int v, int rt)
{
vis[v] = 1;
bool ans = col[v]? 0: 1;
for (int u : A[v]) {
bool canu;
if (vis[u])
canu = u == rt;
else
canu = dfs0(u, rt);
if (col[v])
ans |= canu;
else
ans &= canu;
}
return ans;
}
bool dfs1(int v)
{
vis[v] = 1;
if (charg[v] && can_reach_self[v]) {
win[v] = 1;
return 1;
}
bool ans = col[v]? 0: 1;
for (int u : A[v]) {
bool wu;
if (vis[u])
wu = win[u] == 1;
else
wu = dfs1(u);
if (col[v])
ans |= wu;
else
ans &= wu;
}
win[v] = ans;
return ans;
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> V, std::vector<int> U) {
n = a.size();
m = V.size();
Loop (i,0,n) {
col[i] = a[i];
charg[i] = r[i];
}
Loop (i,0,m) {
int v = V[i], u = U[i];
A[v].push_back(u);
}
Loop (i,0,n) {
memset(vis, 0, sizeof(vis));
can_reach_self[i] = dfs0(i, i);
}
vector<int> ans(n);
Loop (i,0,n) {
memset(vis, 0, sizeof(vis));
memset(win, -1, sizeof(win));
ans[i] = dfs1(i);
}
return ans;
}
