#include "train.h"
#include <bits/stdc++.h>
#define maxn 5005
using namespace std;
int selfLoop[maxn];
vector<int> adj[maxn], Stack, g[maxn];
int reachable[maxn][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 sz = 0;
int v;
do {
v = Stack.back(); ++sz;
Stack.pop_back();
cl[v] = 2;
lt[v] = slt;
} while (v != u);
cool[slt] = (sz > 1 || (selfLoop[v]));
}
}
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 < n; i++) charged[i] = r[i];
for (int i = 0; i < m; i++) {
g[u[i]].emplace_back(v[i]);
if (u[i] == v[i]) {
selfLoop[u[i]] = 1;
continue;
}
if (!charged[u[i]] && !charged[v[i]]) adj[u[i]].emplace_back(v[i]);
}
for (int i = 0; i < n; i++) if (!cl[i] && !charged[i]) pfs(i);
for (int i = 0; i < n; i++) {
fill(cl, cl + n, 0);
cl[i] = 1;
queue<int> q;
q.push(i);
while (!q.empty()) {
int u = q.front(); reachable[i][u] = 1; q.pop();
for (int v : g[u])
if (!cl[v]) {
cl[v] = 1;
q.push(v);
}
}
}
vector<int> ans(n, 1);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (reachable[i][j] && cool[lt[j]]) {ans[i] = 0; break;}
return ans;
}
