#include "train.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5010;
vector<int> haha[MAXN];
vector<int> yeah[MAXN];
vector<bool> bruh(MAXN);
int n;
void calc(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
queue<int> idk;
vector<int> col(n);
for(int i = 0; i < n; i++) {
if(r[i]) {
idk.push(i);
}
}
vector<int> br(n);
vector<bool> yo(n,true);
while(!idk.empty()) {
int x = idk.front();
idk.pop();
if(bruh[x] || !yo[x]) {
continue;
}
yo[x] = false;
col[x] = 1;
for(int v: yeah[x]) {
br[v]++;
if(a[v] == 1) {
if(br[v] == 1) {
idk.push(v);
}
}
else {
if(br[v] == haha[v].size()) {
idk.push(v);
}
}
}
}
while(!idk.empty()) {
idk.pop();
}
for(int i = 0; i < n; i++) {
br[i] = 0;
yo[i] = true;
}
for(int i = 0; i < n; i++) {
if(col[i] == 0) {
idk.push(i);
}
}
while(!idk.empty()) {
int x = idk.front();
col[x] = 0;
idk.pop();
if(!yo[x]) {
continue;
}
yo[x] = false;
for(int v: yeah[x]) {
if(col[v] == 0) {
continue;
}
br[v]++;
if(a[v] == 0) {
if(br[v] == 1) {
idk.push(v);
}
}
else {
if(br[v] == haha[v].size()-1) {
idk.push(v);
}
}
}
}
for(int i = 0; i < n; i++) {
if(col[i] == 0) {
bruh[i] = true;
}
}
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
n = a.size();
int m = u.size();
for(int i = 0; i < m; i++) {
haha[u[i]].push_back(v[i]);
yeah[v[i]].push_back(u[i]);
}
int br = 0;
while(true) {
int z = 0;
calc(a,r,u,v);
for(int i = 0; i < n; i++) {
if(bruh[i]) {
z++;
}
}
if(z > br) {
z = br;
}
else {
break;
}
}
vector<int> ans(n);
for(int i = 0; i < n; i++) {
if(!bruh[i]) {
ans[i] = 1;
}
}
return ans;
}
