#include "train.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g , rg;
int n , m;
vector<bool> ask(vector<int> a , vector<int> r){
vector<bool> ans(n , 0);
vector<int> d(n , 0);
queue<int> b;
for(int i = 0; i < n; i++){
d[i] = g[i].size();
if(r[i]){
ans[i] = 1;
b.push(i);
}
}
while(!b.empty()){
int x = b.front();
b.pop();
for(int y : rg[x]){
if(ans[y])continue;
if(a[y]){
ans[y] = 1;
b.push(y);
continue;
}
d[y]--;
if(d[y] == 0){
ans[y] = 1;
b.push(y);
continue;
}
}
}
return ans;
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
n = a.size();
m = u.size();
g.resize(n);
rg.resize(n);
for(int i = 0; i < m; i++){
g[u[i]].push_back(v[i]);
rg[v[i]].push_back(u[i]);
}
vector<int> ans(n , 0);
vector<int> d(n , 0);
queue<int> b;
vector<bool> o = ask(a , r);
for(int i = 0; i < n; i++){
if(!o[i]){
ans[i] = 1;
r[i] = 0;
b.push(i);
}
}
while(!b.empty()){
int x = b.front();
b.pop();
for(int y : rg[x]){
if(ans[y])continue;
if(!a[y]){
ans[y] = 1;
r[y] = 0;
b.push(y);
continue;
}
d[y]--;
if(d[y] == 0){
ans[y] = 1;
r[y] = 0;
b.push(y);
continue;
}
}
o = ask(a , r);
for(int i = 0; i < n; i++){
if(!o[i] && !ans[i]){
ans[i] = 1;
r[i] = 0;
b.push(i);
}
}
}
for(int i = 0; i < n; i++)ans[i] = !ans[i];
return ans;
}
