// In the name of Allah
#include <bits/stdc++.h>
#include "train.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e4 + 4;
int n, m;
pii A[maxn]; vector<int> lsx;
vector<int> adj[maxn], adjr[maxn];
vector<int> M; queue<int> qu;
int D0[maxn], D1[maxn];
void calx() {
M.clear(); M.resize(n);
for (int i = 0; i < n; i++) {
D0[i] = len(adj[i]); D1[i] = 0;
}
for (int v : lsx) {
M[v] = 1; qu.push(v);
}
while (!qu.empty()) {
int v = qu.front(); qu.pop();
for (int u : adjr[v]) {
D0[u]--; D1[u]++;
if (M[u]) continue;
if (A[u].S == 1 && D1[u] >= 1) {
M[u] = 1; qu.push(u);
}
else if (A[u].S == 0 && D0[u] == 0) {
M[u] = 1; qu.push(u);
}
}
}
}
vector<int> who_wins(vector<int> ax, vector<int> rx, vector<int> ux, vector<int> vx) {
n = len(ax); m = len(ux);
for (int i = 0; i < n; i++) A[i] = Mp(rx[i], ax[i]);
for (int i = 0; i < m; i++) {
int u = ux[i], v = vx[i];
adj[u].pb(v); adjr[v].pb(u);
}
for (int i = 0; i < n; i++) {
if (A[i].F == 1) lsx.pb(i);
}
calx();
while (true) {
int x = -1;
for (int v : lsx) {
if (A[v].S == 1 && D1[v] == 0) {
x = v; break;
}
else if (A[v].S == 0 && D0[v] >= 1) {
x = v; break;
}
}
if (x == -1) break;
lsx.erase(find(all(lsx), x));
calx();
}
return M;
}
