#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ii = pair<int, int>;
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
int N, M, timer, tin[5001], low[5001];
vector<int> adj[5001], S;
bool vis[5001], Scc[5001], station[5001];
bool self[5001];
int DP[5001][5001];
void dfs(int v) {
tin[v] = low[v] = timer++;
S.push_back(v); vis[v] = 1;
for(auto u : adj[v]) {
if(tin[u] == -1) dfs(u);
if(vis[u]) low[v] = min(low[v], low[u]);
}
if(tin[v] == low[v]) {
vector<int> V; bool valid = 0;
while(1) {
int U = S.back(); S.pop_back();
V.push_back(U); vis[U] = 0;
if(station[U]) valid = 1;
if(U == v) break;
}
if(V.size() == 1) return;
for(auto u : V)
Scc[u] = valid;
}
}
int solve(int v, int t) {
if(Scc[v]) return 1;
if(DP[v][t] != -1) return DP[v][t];
if(t) {
for(auto u : adj[v]) {
if(solve(u, t - 1))
return DP[v][t] = 1;
}
}
if(station[v] && adj[v].size() == 0)
return DP[v][t] = 1;
return DP[v][t] = 0;
}
int solve(int v, int t, vector<int> A) {
if(v >= N) return 0;
if(station[v]) t = N;
if(A[v] == 1) {
if(station[v] && self[v])
return 1;
for(auto u : adj[v]) {
if(solve(v + 1, t - 1, A))
return 1;
}
return 0;
}
if(station[v]) {
for(auto u : adj[v])
return solve(v + 1, t - 1, A);
return 0;
}
if(self[v]) return 0;
return solve(v + 1, t - 1, A);
}
vector<int> subtask1(vector<int> A) {
vector<int> res(N, 0);
for(int l = 0; l < N; l++) {
res[l] = solve(l, N, A);
}
return res;
}
vector<int> who_wins(vector<int> A, vector<int> R,
vector<int> U, vector<int> V) {
N = A.size(), M = U.size();
for(int l = 0; l < N; l++)
station[l] = R[l];
bool ok = 1;
for(int l = 0; l < M; l++) {
int u = U[l], v = V[l];
if(u == v) {
Scc[u] = station[u];
self[u] = 1; continue;
}
adj[u].pb(v); ok &= (v == u + 1);
}
if(ok) return subtask1(A);
memset(tin, -1, sizeof tin);
memset(DP, -1, sizeof DP);
for(int l = 0; l < N; l++) {
if(tin[l] != -1) continue;
dfs(l);
}
vector<int> res(N);
for(int l = 0; l < N; l++) {
res[l] = solve(l, N);
}
return res;
}
