#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}
template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
res += static_cast<char>('0' + v[i]);
}
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);
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);
vector<vector<int>> Rev(n);
for (int i = 0; i < m; i++) {
g[From[i]].push_back(To[i]);
Rev[To[i]].push_back(From[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]) {
assert(ret[i] != (player ^ 1));
ret[i] = player;
}
}
}
}
vector<bool> st(n);
vector<int> deg(n);
bool added;
function<void(int, int)> dfs = [&](int v, int player) {
for (int i : Rev[v]) {
if (ret[i] != -1) {
continue;
}
if (st[i]) {
continue;
}
deg[i]--;
if (owned[i] == player || (deg[i] == 0)) {
st[i] = true;
added = true;
dfs(i, player);
}
}
};
auto spanning = [&](vector<bool> &base, int reachable, bool hard = false) {
added = false;
for (int i = 0; i < n; i++) {
deg[i] = 0;
if (ret[i] != -1) {
continue;
}
for (int j : g[i]) {
if (ret[j] == -1 || hard) {
deg[i]++;
}
}
}
st = base;
for (int i = 0; i < n; i++) {
if (base[i]) {
dfs(i, reachable);
}
}
base = st;
return added;
};
while (true) {
vector<bool> bwin(n);
vector<bool> awin(n);
for (int i = 0; i < n; i++) {
if (ret[i] == 0) {
bwin[i] = true;
}
if (ret[i] == 1) {
awin[i] = true;
}
}
bool change = spanning(awin, 1, true) | spanning(bwin, 0, true);
if (!change) {
break;
}
for (int i = 0; i < n; i++) {
if (bwin[i]) {
ret[i] = 0;
}
if (awin[i]) {
ret[i] = 1;
}
assert(!awin[i] || !bwin[i]);
}
}
while (true) {
vector<bool> removed(n);
for (int i = 0; i < n; i++) {
if (ret[i] == -1 && z[i]) {
removed[i] = true;
}
}
spanning(removed, 1);
removed = st;
vector<bool> lost = removed;
bool change = false;
for (int i = 0; i < n; i++) {
if (ret[i] == -1) {
lost[i] = !lost[i];
if (lost[i]) {
change = true;
}
}
}
if (!change) {
break;
}
spanning(lost, 0);
lost = st;
for (int i = 0; i < n; i++) {
if (ret[i] == -1 && lost[i]) {
ret[i] = 0;
}
}
}
for (int i = 0; i < n; i++) {
if (ret[i] == -1) {
ret[i] = 1;
}
}
return ret;
}
