#include <bits/stdc++.h>
using namespace std;
vector<int> who_wins(vector<int> owned, vector<int> z, vector<int> From, vector<int> To) {
int n = owned.size();
int m = To.size();
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
g[From[i]].push_back(To[i]);
}
vector<int> ret(n, -1);
{
vector<int> was(n);
vector<int> alive(n);
function<void(int)> dfs = [&] (int v) {
was[v] = 1;
for (int i : g[v]) {
if (alive[i] && !was[i]) {
dfs(i);
}
}
};
auto winstate = [&](vector<int> keep, vector<int> nodes) {
fill(alive.begin(), alive.end(), 0);
for (int i : keep) {
alive[i] = 1;
}
vector<vector<int>> r(n);
for (int i = 0; i < n; i++) {
if (!alive[i]) {
continue;
}
dfs(i);
r[i] = was;
fill(was.begin(), was.end(), 0);
}
vector<bool> win(n);
for (int i : nodes) {
for (int j : g[i]) {
if (alive[j] && r[j][i] == 1) {
win[i] = true;
}
}
}
return win;
};
auto get_win = [&](vector<int> keep, vector<bool> &win) {
while (true) {
bool change = false;
for (int i : keep) {
if (win[i]) {
continue;
}
for (int j : g[i]) {
if (win[j]) {
win[i] = true;
change = true;
}
}
}
if (!change) {
break;
}
}
};
for (int player = 0; player < 2; player++) {
vector<int> keep;
vector<int> nodes;
for (int i = 0; i < n; i++) {
if (owned[i] != player) {
continue;
}
if (player == 1) {
keep.push_back(i);
if (z[i]) {
nodes.push_back(i);
}
} else {
if (!z[i]) {
keep.push_back(i);
nodes.push_back(i);
}
}
}
vector<bool> win = winstate(keep, nodes);
if (player == 0) {
keep.clear();
for (int i = 0; i < n; i++) {
if (owned[i] == player) {
keep.push_back(i);
}
}
}
get_win(keep, win);
for (int i = 0; i < n; i++) {
if (win[i]) {
ret[i] = player;
}
}
}
}
vector<bool> Ze(n);
while (true) {
bool change = false;
for (int i = 0; i < n; i++) {
if (ret[i] != -1) {
continue;
}
if (Ze[i]) {
continue;
}
bool ok = false;
if (owned[i] == 1) {
for (int j : g[i]) {
if (ret[j] != -1) {
continue;
}
if (Ze[j] || z[j]) {
ok = true;
}
}
} else {
bool rev = false;
for (int j : g[i]) {
if (ret[j] != -1) {
continue;
}
if (Ze[j] || z[j]) {
continue;
}
rev = true;
}
ok = !rev;
}
if (ok) {
Ze[i] = true;
change = true;
}
}
if (!change) {
break;
}
}
for (int i = 0; i < n; i++) {
if (ret[i] == -1) {
if (Ze[i]) {
ret[i] = 1;
} else {
ret[i] = 0;
}
}
}
return ret;
}
