#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
const int MOD = 1e9+7;
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define bk back()
#define all(x) begin(x), end(x)
const int mx = 5005;
int n, m;
vi a, r, u, v;
vi adj[mx];
vi radj[mx];
bool bad[mx];
int getBType(){
for(int i = 0; i < n; i++){
if(bad[i]) continue;
if(a[i] == 1){
bool works = 1;
for(auto u: adj[i]){
if(!bad[u]){
works = 0;
break;
}
}
if(works){
return i;
}
}
else{
for(auto u: adj[i]){
if(bad[u]){
return i;
}
}
}
}
return -1;
}
array<bool, mx> dp;
array<bool, mx> ndp;
bool forced[mx];
int cur_deg[mx]; //number of neighbors that can be forced into a good C
int bad_cur_deg[mx];
int self[mx];
queue<int> to_unForce;
void iForce(int node){
for(auto u: radj[node]){
if(forced[u] || bad[u]) continue;
if(a[u] == 0){
cur_deg[u]++;
//cout << u << " " << cur_deg[u] << "\n";
if(cur_deg[u] == sz(adj[u])){
forced[u] = 1;
to_unForce.push(u);
}
}
else{
forced[u] = 1;
to_unForce.push(u);
}
}
}
void initForce(){
for(int i = 0; i < n; i++){
forced[i] = 0;
}
for(int i = 0; i < n; i++){
if(bad[i]) continue;
if(r[i] == 1){
if(!forced[i]){
forced[i] = 1;
to_unForce.push(i);
}
}
}
while(sz(to_unForce)){
int node = to_unForce.front();
to_unForce.pop();
iForce(node);
}
}
int getAType(){
initForce();
for(int i = 0; i < n; i++){
if(!bad[i] && !forced[i] && a[i] == 1){
return i;
}
}
return -1;
}
vi who_wins(vi _a, vi _r, vi _u, vi _v) {
a = _a;
r = _r;
u = _u;
v = _v;
n = sz(a);
m = sz(u);
for(int i = 0; i < m; i++){
adj[u[i]].pb(v[i]);
radj[v[i]].pb(u[i]);
}
for(int i = 0; i < n; i++){
for(auto u: adj[i]){
if(u == i) self[i]++;
}
}
for(int i = 0; i < n; i++){
dp[i] = 1;
if(r[i] == 1) dp[i] = 0;
}
for(int rep = 0; rep < mx; rep++){
for(int i = 0; i < n; i++){
ndp[i] = 0;
}
for(int i = 0; i < n; i++){
if(r[i] == 1) continue;
if(a[i] == 1){
ndp[i] = 1;
for(auto u: adj[i]){
if(dp[u] == 0) ndp[i] = 0;
}
}
else{
ndp[i] = 0;
for(auto u: adj[i]){
if(dp[u] == 1) ndp[i] = 1;
}
}
}
swap(dp, ndp);
}
for(int i = 0; i < n; i++){
if(dp[i] == 1){
bad[i] = 1;
//cout << "initial bad: " << i << "\n";
}
}
while(true){
int node = getBType();
if(node == -1){
node = getAType();
}
if(node == -1) break;
bad[node] = 1;
}
vi ans(n, 0);
for(int i = 0; i < n; i++){
if(!bad[i]){
ans[i] = 1;
}
}
return ans;
}
