%:include "train.h"
%:include <bits/stdc++.h>
%:define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
%:define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 5050;
bool rem[N];
bool owner[N];
bool charg[N];
vector<int> A[N], T[N];
vector<int> V;
void remove(const vector<int> &vec)
{
for (int v : vec)
rem[v] = 1;
Loop (i,0,V.size()) {
if (rem[V[i]]) {
swap(V[i], V.back());
V.pop_back();
--i;
}
}
for (auto *E : {A, T}) for (int v : V) {
Loop (i,0,E[v].size()) {
if (rem[E[v][i]]) {
swap(E[v][i], E[v].back());
E[v].pop_back();
--i;
}
}
}
}
int cnt[N];
bool vis[N];
void dfs(int v, bool o)
{
vis[v] = 1;
for (int u : T[v]) {
++cnt[u];
if (!vis[u] && (owner[u] == o || cnt[u] == A[u].size()))
dfs(u, o);
}
}
vector<int> f(const vector<int> &vec, bool o)
{
for (int v : vec) {
if (!rem[v] && !vis[v])
dfs(v, o);
}
vector<int> ans;
for (int v : V) {
if (vis[v])
ans.push_back(v);
vis[v] = 0;
cnt[v] = 0;
}
return ans;
}
vector<int> cmpl(const vector<int> &vec)
{
vector<int> ans;
static bool a[N];
for (int v : vec)
a[v] = 1;
for (int v : V) {
if (!a[v])
ans.push_back(v);
}
for (int v : vec)
a[v] = 0;
return ans;
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> vv, std::vector<int> uu)
{
int n = a.size();
V.resize(n);
iota(V.begin(), V.end(), 0);
vector<int> charg;
Loop (i,0,n) {
owner[i] = a[i];
if (r[i])
charg.push_back(i);
}
Loop (i,0,vv.size()) {
int v = vv[i], u = uu[i];
A[v].push_back(u);
T[u].push_back(v);
}
vector<int> ans;
for (;;) {
auto vec = f(charg, 1);
if (vec.size() == V.size()) {
ans = V;
break;
}
if (vec.size() == 0)
break;
auto vec2 = f(cmpl(vec), 0);
remove(vec2);
}
vector<int> res(n);
for (int v : ans)
res[v] = 1;
return res;
}
