#include <bits/stdc++.h>
#include "train.h"
using namespace std;
const int MAX_N = 5005;
const int MAX_M = 20005;
int N, M;
vector <int> graph[MAX_N];
int A[MAX_N], R[MAX_N];
bool visited[MAX_N];
bool self[MAX_N], nxt[MAX_N];
bool dfs(int u, int x) {
visited[u] = true;
for (auto v : graph[u]) {
if (v == x) return true;
if (visited[v] == false and dfs(v, x) == true) return true;
}
return false;
}
bool dfs2(int u) {
visited[u] = true;
if (R[u] == 1) return true;
for (auto v : graph[u]) {
if (visited[v] == false and dfs2(v) == true) return true;
}
return false;
}
vector <int> who_wins(vector <int> a, vector <int> r, vector <int> u, vector <int> v) {
N = a.size(), M = u.size();
for (int i = 0; i < N; i++) A[i] = a[i], R[i] = r[i];
bool sub1 = true;
for (int i = 0; i < M; i++) {
if (u[i] != v[i] and u[i] != v[i] - 1) sub1 = false;
if (u[i] == v[i]) self[u[i]] = true;
else if (u[i] + 1 == v[i]) nxt[u[i]] = true;
graph[u[i]].push_back(v[i]);
}
vector <int> ans(N, 0);
if (sub1 == true) {
bool ok = R[N - 1];
for (int i = N - 1; i >= 0; i--) {
if (self[i] == true) {
if (R[i] == 1 and A[i] == 1) ok = true;
else if (R[i] == 0 and A[i] == 0) ok = false;
}
ans[i] = ok;
if (i > 0 and nxt[i - 1] == false) ok = R[i - 1];
}
}
else {
for (int s = 0; s < N; s++) {
if (R[s] == 0) continue;
for (int i = 0; i < N; i++) visited[i] = false;
if (dfs(s, s) == false) R[s] = 0;
}
for (int s = 0; s < N; s++) {
for (int i = 0; i < N; i++) visited[i] = false;
ans[s] = dfs2(s);
}
}
return ans;
}
