#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false); cin.tie(0);
#define pre(a) cout << fixed; cout.precision(a)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define em emplace
#define eb emplace_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;
int n, m;
vector<int> g[5010];
vector<int> rg[5010];
vector<int> w;
vector<int> A;
vector<bool> canGo(vector<int> &x, int c) {
int deg[5010] = {};
vector<bool> chk(n, 0);
vector<int> ret;
queue<int> q;
for(int i=0; i<n; i++) {
if(w[i] != -1) continue;
for(int j : g[i])
if(w[j] == -1) deg[i]++;
}
for(auto i : x)
chk[i] = true, q.em(i);
while(q.size()) {
int cur = q.front();
q.pop();
for(auto i : rg[cur]) {
if(chk[i] || w[i] != -1) continue;
if(A[i] == c) {
chk[i] = true;
q.em(i);
}
else {
deg[i]--;
if(deg[i] == 0) chk[i] = true, q.em(i);
}
}
}
for(int i=0; i<n; i++)
if(chk[i]) ret.eb(i);
return chk;
}
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();
A = a;
w.resize(n, -1);
for(int i=0; i<m; i++) {
g[u[i]].eb(v[i]);
rg[v[i]].eb(u[i]);
}
int cnt = 1;
while(cnt) {
vector<int> x, y;
for(int i=0; i<n; i++)
if(r[i] && w[i] == -1) x.eb(i);
auto v = canGo(x, 1);
for(int i=0; i<n; i++)
if(w[i] == -1 && !v[i]) y.eb(i);
if(y.empty()) {
for(int i=0; i<n; i++)
if(w[i] == -1) w[i] = 1;
break;
}
else {
v = canGo(y, 0);
for(int i=0; i<n; i++)
if(v[i]) w[i] = 0;
}
}
return w;
}
