#include "train.h"
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define sz(x) (int((x).size()))
vi who_wins(vi a, vi r, vi u, vi v) {
int n = sz(a), m = sz(u);
vvi G(n), R(n); for (int i = 0; i < m; i++) G[u[i]].push_back(v[i]), R[v[i]].push_back(u[i]);
bitset<5000> alive; for (int i = 0; i < n; i++) alive.set(i);
auto find_all = [&](int owner, bitset<5000> &base) {
vi deg(n);
for (int i = alive._Find_first(); i < n; i = alive._Find_next(i)) {
for (auto v : R[i]) {
if (!alive[v]) continue;
deg[v]++;
}
}
bitset<5000> r;
vector<int> st; for (int x = base._Find_first(); x < n; x = base._Find_next(x)) st.push_back(x), r[x] = 1;
while (!st.empty()) {
int u = st.back(); st.pop_back();
for (auto v : R[u]) {
if (!alive[v]) continue;
if (r[v]) continue;
if (a[v] == owner || --deg[v] == 0) st.push_back(v), r[v] = 1;
}
}
return r;
};
vi res(n, 1); bitset<5000> ar; for (int i = 0; i < n; i++) ar[i] = r[i];
while (true) {
bitset<5000> far = find_all(1, ar);
if (far.count() == alive.count()) break;
bitset<5000> x; for (int i = alive._Find_first(); i < n; i = alive._Find_next(i)) if (!far[i]) x[i] = 1;
bitset<5000> fbr = find_all(0, x);
for (int u = fbr._Find_first(); u < n; u = fbr._Find_next(u)) alive[u] = 0, res[u] = 0, ar[u] = 0;
}
return res;
}
