#include "train.h"
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define sz(x) (int((x).size()))
struct SCC {
int n, c = 0; vvi G, R;
vi scc, len, topo, selfloop;
vvi Gs, nodes;
SCC(int N, vvi &g) {
n = N; G = g; R.assign(n, vi());
for (int i = 0; i < n; i++) {
for (auto j : G[i]) R[j].push_back(i);
}
scc.assign(n, -1);
vi order1, cmp1(n, -1);
for (int i = 0; i < n; i++) {
if (cmp1[i] != -1) continue;
cmp1[i] = c++;
dfs(i, order1, cmp1, G);
}
c = 0; vi order2;
reverse(all(order1));
for (auto i : order1) {
if (scc[i] != -1) continue;
scc[i] = c++;
dfs(i, order2, scc, R);
}
vi deg(c, 0), st; len.assign(c, 0); selfloop.assign(c, 0);
set<pi> used;
Gs.assign(c, vi()); nodes.assign(c, vi());
for (int i = 0; i < n; i++) {
nodes[scc[i]].push_back(i); len[scc[i]]++;
for (auto j : G[i]) {
if (scc[i] == scc[j]) {selfloop[scc[i]] = 1; continue;}
if (used.count({scc[i], scc[j]})) continue;
Gs[scc[i]].push_back(scc[j]);
used.insert({scc[i], scc[j]});
deg[scc[j]]++;
}
}
for (int i = 0; i < c; i++) if (deg[i] == 0) st.push_back(i);
while (!st.empty()) {
int u = st.back(); st.pop_back();
topo.push_back(u);
for (auto v : Gs[u]) {
if (--deg[v] == 0) st.push_back(v);
}
}
reverse(topo.begin(), topo.end());
}
void dfs(int u, vi &order, vi &cmp, vvi &G) {
for (auto v : G[u]) {
if (cmp[v] != -1) continue;
cmp[v] = cmp[u];
dfs(v, order, cmp, G);
}
order.push_back(u);
}
bool has_cycle(int cmp) {
return selfloop[cmp];
}
};
int n, m;
vi charging, owner, scc;
vvi G, R, Ag, Ar, Bg, Br, Cg, Cr;
vi who_wins(vi a, vi r, vi u, vi v) {
n = sz(a), m = sz(u);
charging = r; owner = a;
G.assign(n, vi()); R.assign(n, vi());
Ag.assign(n, vi()); Ar.assign(n, vi());
Bg.assign(n, vi()); Br.assign(n, vi());
Cg.assign(n, vi()); Cr.assign(n, vi());
for (int i = 0; i < m; i++) {
G[u[i]].push_back(v[i]), R[v[i]].push_back(u[i]);
if (a[u[i]] == a[v[i]]) {
if (a[u[i]] == 1) {
Ag[u[i]].push_back(v[i]), Ar[v[i]].push_back(u[i]);
} else if (a[u[i]] == 0) {
if (r[u[i]] == 0 && r[v[i]] == 0) Bg[u[i]].push_back(v[i]), Br[v[i]].push_back(u[i]);
Cg[u[i]].push_back(v[i]), Cr[v[i]].push_back(u[i]);
}
}
}
auto ascc = SCC(n, Ag);
auto bscc = SCC(n, Bg);
auto cscc = SCC(n, Cg);
auto scc = SCC(n, G);
int c1 = ascc.c; vi agood(c1, 0);
int c2 = cscc.c; vi bgood(c2, 0);
for (int i = 0; i < n; i++) {
agood[ascc.scc[i]] |= charging[i] & ascc.has_cycle(ascc.scc[i]);
bgood[cscc.scc[i]] |= bscc.has_cycle(bscc.scc[i]);
}
for (int x = 0; x < n+5; x++) {
for (auto u : ascc.topo) {
for (auto v : ascc.Gs[u]) {
agood[u] |= agood[v];
}
}
for (auto u : cscc.topo) {
for (auto v : cscc.Gs[u]) {
bgood[u] |= bgood[v];
}
}
for (int i = 0; i < n; i++) {
for (auto v : G[i]) {
if (owner[i] == 1 && owner[v] == 0) agood[ascc.scc[i]] |= !bgood[cscc.scc[v]];
if (owner[i] == 0 && owner[v] == 1) {
bgood[cscc.scc[i]] |= !agood[ascc.scc[v]];
}
}
}
}
vi res(n, 0);
for (int i = 0; i < n; i++) if (owner[i] == 1 && agood[ascc.scc[i]]) res[i] = 1;
for (int i = 0; i < n; i++) if (owner[i] == 0 && !bgood[cscc.scc[i]]) res[i] = 1;
return res;
}
