#include "train.h"
#include <bits/stdc++.h>
#define maxn 5005
using namespace std;
int selfLoop[maxn];
vector<int> adj[maxn], Stack, g[maxn];
int cl[maxn], num[maxn], low[maxn], lt[maxn], slt = 0, cool[maxn], id = 0, charged[maxn];
void pfs(int u) {
num[u] = low[u] = ++id;
cl[u] = 1;
Stack.emplace_back(u);
for (int v : adj[u])
if (!cl[v]) {
pfs(v);
low[u] = min(low[u], low[v]);
} else if (cl[v] == 1) low[u] = min(low[u], num[v]);
if (num[u] == low[u]) {
++slt;
int hasCharged = 0, sz = 0;
int v;
do {
v = Stack.back(); ++sz;
hasCharged |= (charged[v]);
Stack.pop_back();
cl[v] = 2;
lt[v] = slt;
} while (v != u);
cool[slt] = ((sz > 1 || (selfLoop[v])) && (hasCharged));
}
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
int n = a.size(), m = u.size();
for (int i = 0; i < m; i++) {
if (u[i] == v[i]) selfLoop[u[i]] = 1;
else adj[u[i]].emplace_back(v[i]);
}
for (int i = 0; i < n; i++) charged[i] = r[i];
for (int i = 0; i < n; i++) if (!cl[i]) pfs(i);
for (int i = 0; i < m; i++)
if (lt[u[i]] != lt[v[i]])
g[lt[u[i]]].emplace_back(lt[v[i]]);
for (int i = 1; i <= slt; i++)
for (int j : g[i]) {
assert(j < i);
cool[i] |= cool[j];
}
vector<int> ans;
for (int i = 0; i < n; i++) ans.emplace_back(cool[lt[i]]);
return ans;
}
