#include "train.h"
#include "bits/stdc++.h"
using namespace std;
vector <int> g[5005];
vector <int> trans[5005];
int own[5005];
int charge[5005];
int n;
int m;
int out[5005];
bool take[5005];
bool del[5005];
int outdeg[5005];
vector <int> Fa(vector <int> v) {
for(int i = 0; i < n; i++) {
out[i] = 0;
take[i] = false;
}
queue <int> q;
for(auto i : v) {
q.push(i);
take[i] = true;
}
while(!q.empty()) {
int i = q.front();
q.pop();
for(auto j : trans[i]) {
if(del[j]) continue;
out[j] += 1;
if(!take[j] && own[j] == 1) {
q.push(j);
take[j] = true;
}
if(!take[j] && out[j] == outdeg[j] && own[j] == 0) {
q.push(j);
take[j] = true;
}
}
}
vector <int> ans;
for(int i = 0; i < n; i++) {
if(take[i]) {
ans.emplace_back(i);
}
}
return ans;
}
vector <int> Fb(vector <int> v) {
for(int i = 0; i < n; i++) {
out[i] = 0;
take[i] = false;
}
queue <int> q;
for(auto i : v) {
q.push(i);
take[i] = true;
}
while(!q.empty()) {
int i = q.front();
q.pop();
for(auto j : trans[i]) {
if(del[j]) continue;
out[j] += 1;
if(!take[j] && own[j] == 0) {
q.push(j);
take[j] = true;
}
if(!take[j] && out[j] == outdeg[j] && own[j] == 1) {
q.push(j);
take[j] = true;
}
}
}
vector <int> ans;
for(int i = 0; i < n; i++) {
if(take[i]) {
ans.emplace_back(i);
}
}
return ans;
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
vector <int> ans;
n = a.size();
m = u.size();
ans.resize(n);
for(int i = 0; i < n; i++) {
own[i] = a[i];
charge[i] = r[i];
del[i] = false;
}
for(int i = 0; i < m; i++) {
int p = u[i];
int q = v[i];
g[p].emplace_back(q);
trans[q].emplace_back(p);
++outdeg[p];
}
while(true) {
vector <int> station;
for(int i = 0; i < n; i++) {
if(charge[i] && !del[i]) {
station.emplace_back(i);
}
}
vector <int> P = Fa(station);
vector <int> Q;
for(int i = 0; i < n; i++) {
if(!take[i] && !del[i]) {
Q.emplace_back(i);
}
}
if(Q.empty()) {
for(auto i : P) {
ans[i] = 1;
}
break;
}
vector <int> X = Fb(Q);
for(auto i : X) {
ans[i] = 0;
del[i] = true;
for(auto j : trans[i]) {
--outdeg[j];
}
}
}
return ans;
}
