#include <bits/stdc++.h>
#include "train.h"
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const int N = 5007;
int n, m;
int a[N], r[N], rdeg[N];
vector <int> adj[N];
vector <int> f(int o, vector <int> v) {
queue <int> q;
vector <int> deg(n, 0);
for (int i = 0; i < n; i++) if (v[i]) q.push(i);
while (!q.empty()) {
int x = q.front(); q.pop();
for (int y : adj[x]) if (!v[y]) {
deg[y]++;
if (a[y] == o) v[y] = 1, q.push(y);
else if (deg[y] == rdeg[y]) v[y] = 1, q.push(y);
}
}
return v;
}
vector <int> who_wins(vector <int> aa, vector <int> rr, vector <int> u, vector <int> v) {
n = aa.size(), m = u.size();
for (int i = 0; i < n; i++) a[i] = aa[i], r[i] = rr[i];
for (int i = 0; i < m; i++) adj[v[i]].pb(u[i]), rdeg[u[i]]++;
vector <int> d(n, 1);
while (1) {
vector <int> u(n, 1), c(n, 0);
for (int i = 0; i < n; i++) if (d[i] && r[i]) c[i] = 1;
c = f(1, c);
int ok = 1;
for (int i = 0; i < n; i++) {
if (d[i] && c[i]) u[i] = 0;
if (d[i] && !c[i]) ok = 0;
}
if (ok) break;
u = f(0, u);
for (int i = 0; i < n; i++) if (d[i] && u[i]) d[i] = 0;
}
return d;
}
