#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 solve(vi &a, vi &r, vi &u, vi &v, set<int> &removed) {
return solve(a, r, u, v, removed);
}
vi who_wins(vi a, vi r, vi u, vi v) {
int n = sz(a), m = sz(u);
vector<set<int>> G(n, set<int>()), R(n, set<int>());
for (int i = 0; i < m; i++) {
G[u[i]].insert(v[i]), R[v[i]].insert(u[i]);
}
set<int> removed;
vi res(n, 0);
vi deg1(n, 0), deg2(n, 0);
while (true) {
set<int> far;
vi st; for (int i = 0; i < n; i++) if (!removed.count(i) && r[i]) st.push_back(i), far.insert(i);
vi deg1(n); for (int i = 0; i < n; i++) deg1[i] = G[i].size();
while (!st.empty()) {
int u = st.back(); st.pop_back();
for (auto v : R[u]) {
if (far.count(v)) continue;
if (a[v] == 1 || --deg1[v] == 0) {
far.insert(v);
st.push_back(v);
}
}
}
if (far.size() + removed.size() == n) {
vi x(n, 0); for (int i = 0; i < n; i++) if (!removed.count(i)) x[i] = 1;
return x;
}
vi st2, removed2;
for (int i = 0; i < n; i++) if (!far.count(i) && !removed.count(i)) removed.insert(i), st2.push_back(i), removed2.push_back(i);
vi deg2(n); for (int i = 0; i < n; i++) deg2[i] = G[i].size();
while (!st2.empty()) {
int u = st2.back(); st2.pop_back();
for (auto v : R[u]) {
if (removed.count(v)) continue;
if (a[v] == 0 || --deg2[v] == 0) {
removed.insert(v);
removed2.push_back(v);
st2.push_back(v);
}
}
}
for (auto v : removed2) {
for (auto u : R[v]) G[u].erase(v);
}
}
return res;
}
