#include "train.h"

// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

const int N = 5005;

int n, A[N], R[N], cur[N], ct[N];

vector<int> g[N], h[N];

bool st[N], in[N];

int q[N];

vector<int> calc(vector<int> S, vector<int> T, int o) {
	for (int v: S) in[v] = 1;
	int hh = 1, tt = 0;
	for (int v: T) st[v] = 1, q[++tt] = v;
	for (int v: S) {
		ct[v] = 0;
		for (int z: g[v]) if (in[z]) ct[v]++; 
	}
	while (hh <= tt) {
		int u = q[hh++];
		for (int v: h[u]) {
			if (!in[v]) continue;
			cur[v]++;
			if (!st[v]) {
				if (A[v] == o || (cur[v] == ct[v])) {
					st[v] = 1;
					q[++tt] = v;
				}
			}
		}
	}
	vector<int> w;
	for (int v: S) {
		if (st[v]) w.pb(v);
		 st[v] = 0, cur[v] = 0;
		 in[v] = ct[v] = 0;
	}
	return w;
}

bool vs[N];

vector<int> er(vector<int> a, vector<int> b) {
	for (int v: b) vs[v] = 1;
	vector<int> c; for (int v: a) if (!vs[v]) c.pb(v);
	for (int v: b) vs[v] = 0;
	return c; 
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> U, std::vector<int> V) {
	n = a.size();
	for (int i = 1; i <= n; i++) {
		A[i] = a[i - 1], R[i] = r[i - 1];
	}
	for (int i = 0; i < U.size(); i++) {
		U[i]++, V[i]++;
		g[U[i]].pb(V[i]), h[V[i]].pb(U[i]);
	}
	std::vector<int> res(n, 0);
	vector<int> w; for (int i = 1; i <= n; i++) w.pb(i);
	while (w.size()) {
		vector<int> s;
		for (int i: w) if (R[i]) s.pb(i);
		vector<int> t = calc(w, s, 1);
		if (t == w) break;
		vector<int> B = er(w, t);
		vector<int> SB = calc(w, B, 0);
		w = er(w, SB);
	}
	for (int v: w) res[v - 1] = 1;
	return res;
}