#include "train.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define len(x) int((x).size())
using i64 = long long;
constexpr int N = 5005;
int n, m;
bool a[N], r[N];
vector<int> adj[N], adjR[N];
int ti, dfn[N], low[N], col[N];
int top, st[N];
int tot;
void tarjan(int u) {
dfn[u] = low[u] = ++ti, st[++top] = u;
for (int v : adj[u]) {
if (a[v] == 1 || r[v] == 1) {
continue;
}
if (dfn[v] == 0) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (col[v] == 0) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
++tot;
int x;
do {
x = st[top--], col[x] = tot;
} while (x != u);
}
}
bool hasV[N], hasE[N], ok[N];
void dfsMark(int u) {
if (ok[u]) {
return;
}
for (int v : adjR[u]) {
if (a[v] == 0) {
dfsMark(v);
}
}
}
vector<int> who_wins(vector<int> a_, vector<int> r_, vector<int> u,
vector<int> v) {
n = len(a_);
memcpy(a + 1, a_.data(), n * sizeof a[0]);
memcpy(r + 1, r_.data(), n * sizeof a[0]);
m = len(u);
for (int i = 0; i < m; ++i) {
++u[i], ++v[i];
adj[u[i]].push_back(v[i]);
adjR[v[i]].push_back(u[i]);
}
for (int i = 1; i <= n; ++i) {
if (dfn[i] == 0 && a[i] == 0 && r[i] == 0) {
tarjan(i);
}
}
for (int i = 0; i < m; ++i) {
const int x = col[u[i]], y = col[v[i]];
if (x == y) {
hasE[x] = true;
}
}
for (int i = 1; i <= n; ++i) {
if (r[i] == 1) {
hasV[col[i]] = true;
}
}
bool any = false;
for (int i = 1; i <= n; ++i) {
if (a[i] == 1 && r[i] == 1) {
any = true;
break;
}
}
if (any) {
for (int i = 1; i <= n; ++i) {
if (a[i] == 0 && !hasV[col[i]] && hasE[col[i]]) {
dfsMark(i);
}
}
vector<int> ans(n);
for (int i = 1; i <= n; ++i) {
if (ok[i]) {
ans[i - 1] = 1;
}
}
return ans;
} else {
bool fl = false;
for (int i = 1; i <= tot; ++i) {
if (!hasV[i] && hasE[i]) {
fl = true;
break;
}
}
return vector<int>(n, fl);
}
}
