#include <bits/stdc++.h>
#include "train.h"
using namespace std;
const int N = 5e3 + 12;
vector<int> g[N],gt[N];
vector<int> a,r;
int n;
vector<int> make(vector<int> t) {
vector<bool> vis(n,false),gd(n,false),l(n,false);
for(int i:t) {
l[i] = 1;
}
vector<int> col(n,0),bf;
for(int i:t) {
for(int to:g[i]) {
if(l[to]) {
col[i]++;
}
}
}
bf = col;
queue<int> q;
for(int i:t) {
if(r[i]) {
vis[i] = 1;
q.push(i);
}
}
while(!q.empty()) {
int v = q.front();q.pop();
gd[v] = 1;
for(int to:gt[v]) {
if(vis[to] || !l[to]) continue;
if(a[to] == 1) {
q.push(to);
vis[to] = 1;
} else {
col[to]--;
if(!col[to]) {
q.push(to);
vis[to] = 1;
}
}
}
}
vis.assign(n,false);
col = bf;
for(int i:t) {
if(!gd[i]) {
q.push(i);
vis[i] = 1;
}
}
while(!q.empty()) {
int v = q.front();q.pop();
gd[v] = 0;
for(int to:gt[v]) {
if(!l[to] || vis[to])continue;
if(!a[to]) {
q.push(to);
vis[to] = 1;
} else {
col[to]--;
if(!col[to]) {
q.push(to);
vis[to] = 1;
}
}
}
}
vector<int> ret;
for(int i:t) {
if(gd[i]) ret.push_back(i);
}
return ret;
}
vector<int> who_wins(vector<int> a_, vector<int> r_, vector<int> u, vector<int> v) {
a = a_;
r = r_;
n = (int)a.size();
for(int i = 0;i < (int)u.size();i++) {
g[u[i]].push_back(v[i]);
gt[v[i]].push_back(u[i]);
}
vector<int> f(n),res(n,0);
iota(f.begin(),f.end(),0);
// f = make(f);
for(int i = 0;i < n;i++) {
f = make(f);
}
for(int i:f) {
res[i] = 1;
}
return res;
}
