#include "train.h"
#include <vector>
#include <queue>
using namespace std;
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
int n = a.size(), m = u.size();
vector<int> w(n, false);
vector<bool> curr(n, true);
vector<vector<int>> prv(n, vector<int>()), nxt(n, vector<int>());
for (int i = 0; i < m; ++i) {
prv[v[i]].push_back(u[i]);
nxt[u[i]].push_back(v[i]);
}
while (true) {
vector<bool> s(n, false);
queue<int> q;
for (int i = 0; i < n; ++i)
if (curr[i] && r[i]) {
s[i] = true;
q.push(i);
}
while (!q.empty()) {
auto y = q.front();
q.pop();
for (auto x: prv[y])
if (curr[x] && !s[x]) {
if (!a[x]) {
bool isGood = true;
for (auto z: nxt[x])
if (curr[z] && !s[z]) {
isGood = false;
break;
}
if (!isGood)
continue;
}
s[x] = true;
q.push(x);
}
}
bool allS = true;
for (int i = 0; i < n; ++i)
if (s[i] != curr[i]) {
allS = false;
break;
}
if (allS) {
for (int i = 0; i < n; ++i)
w[i] = s[i];
break;
}
vector<bool> nonS(n, false);
for (int i = 0; i < n; ++i)
if (curr[i])
nonS[i] = !s[i];
for (int i = 0; i < n; ++i)
if (curr[i] && nonS[i])
q.push(i);
while (!q.empty()) {
auto y = q.front();
q.pop();
for (auto x: prv[y])
if (curr[x] && !nonS[x]) {
if (a[x]) {
bool isGood = true;
for (auto z: nxt[x])
if (curr[z] && !nonS[z]) {
isGood = false;
break;
}
if (!isGood)
continue;
}
nonS[x] = true;
q.push(x);
}
}
for (int i = 0; i < n; ++i)
if (curr[i] && nonS[i])
curr[i] = false;
}
return w;
}
