#include "train.h"
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;
const int N = 5e3 + 7;
int n, m;
unordered_set<int> R;
vector<int> g[N], g1[N];
vector<int> A;
unordered_set<int> cur;
unordered_set<int> rev(const unordered_set<int> &fi){
cur.clear();
for (int i = 0; i < n; ++i){
if (fi.count(i) == 0)cur.insert(i);
}
return cur;
}
queue<int> q;
unordered_set<int> Fw(int w, const unordered_set<int> &fi){
cur = fi;
while (!q.empty())q.pop();
for (int x : fi)
q.push(x);
while (!q.empty()){
auto it = q.front(); q.pop();
for (auto to : g1[it]){
if (cur.count(to) == 1)
continue;
bool __b = all_of(g[to].begin(), g[to].end(), [&](const int &x){return cur.count(x) == 1; });
if (A[to] == w || __b)
{
cur.insert(to);
q.push(to);
}
}
}
return cur;
}
unordered_set<int> All;
unordered_set<int> merge(const unordered_set<int> &fi, const unordered_set<int> &se){
All.clear();
for (auto it : fi)
if (se.count(it) == 1) All.insert(it);
return All;
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
::n = a.size();
::A = a;
::m = u.size();
vector<int> res;
for (int i = 0; i < n; ++i)
if (r[i] == 1) R.insert(i);
for (int i = 0; i < m; ++i){
g[u[i]].push_back(v[i]);
g1[v[i]].push_back(u[i]);
}
unordered_set<int> M;
while (true){
auto R_ex = Fw(1, R);
auto X = rev(R_ex);
auto X_ex = Fw(0, X);
M = merge(R, X_ex);
for (auto it : M)
R.erase(it);
if (M.size() == 0){
auto ans = vector<int>(n, 1);
for (const auto &it : X_ex)
ans[it] = 0;
return ans;
}
}
return res;
}
