#include "train.h"
#include <bits/stdc++.h>
using namespace std;
constexpr size_t N = 5000;
vector<int> g[N], rg[N], postorder, scc[N], scc_non_charge[N];
bitset<N> visited, is_charging, f, deleted;
int ind[N];
void postorder_dfs(int u)
{
visited[u] = 1;
for (auto const &v : g[u])
if (!visited[v] && !deleted[v])
postorder_dfs(v);
postorder.push_back(u);
}
void find_scc(int u, size_t s)
{
visited[u] = 1;
scc[s].push_back(u);
ind[u] = s;
for (auto const &v : rg[u])
if (!visited[v])
find_scc(v, s);
}
void find_scc_non_charge(int u, size_t s)
{
visited[u] = 1;
scc_non_charge[s].push_back(u);
for (auto const &v : rg[u])
if (!visited[v] && !deleted[v])
find_scc(v, s);
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
size_t const n = a.size(), m = u.size();
int subtask = 1;
for (size_t i = 0; i < m; ++i)
if (u[i] != v[i] && u[i] + 1 != v[i])
{
subtask = 3;
break;
}
vector<int> w(n);
if (subtask == 1)
{
vector<bool> has_edge(n), has_loop(n);
for (size_t i = 0; i < m; ++i)
{
if (u[i] == v[i])
has_loop[u[i]] = 1;
else
has_edge[u[i]] = 1;
}
for (size_t i = 0; i < n; ++i)
{
for (size_t j = i; j < n; ++j)
if (has_loop[j])
{
if (!(a[j] ^ r[j]))
{
w[i] = a[j];
break;
}
if (!has_edge[j])
{
w[i] = !a[j];
break;
}
}
}
return w;
}
for (size_t i = 0; i < n; ++i)
is_charging[i] = r[i];
for (size_t i = 0; i < m; ++i)
g[u[i]].push_back(v[i]), rg[v[i]].push_back(u[i]);
for (size_t i = 0; i < n; ++i)
if (!visited[i])
postorder_dfs(i);
visited.reset();
size_t s = 0;
for (auto it = postorder.rbegin(); it != postorder.rend(); ++it)
if (!visited[*it])
{
find_scc(*it, s++);
}
for (int &x : a)
if (!x)
{
subtask = 4;
break;
}
if (subtask == 3)
{
for (size_t i = 0; i < s; ++i)
{
bool has_charging_node = 0;
for (int u : scc[i])
has_charging_node |= r[u];
bool has_cycle = scc[i].size() > 1;
for (int u : scc[i])
for (int v : g[u])
has_cycle |= u == v;
if (has_cycle && has_charging_node)
{
f[i] = 1;
}
}
}
else
{
for (size_t i = 0; i < n; ++i)
deleted[i] = r[i];
visited.reset();
postorder.clear();
for (size_t i = 0; i < n; ++i)
if (!visited[i] && !deleted[i])
postorder_dfs(i);
visited.reset();
size_t t = 0;
for (auto it = postorder.rbegin(); it != postorder.rend(); ++it)
if (!visited[*it])
{
find_scc_non_charge(*it, t++);
}
for (size_t i = 0; i < t; ++i)
{
bool has_cycle = scc_non_charge[i].size() > 1;
for (int u : scc_non_charge[i])
for (int v : g[u])
has_cycle |= u == v;
if (has_cycle)
{
f[ind[scc_non_charge[i][0]]] = 1;
}
}
}
for (size_t i = s - 1; i < s; --i)
if (f[i])
{
for (auto const u : scc[i])
for (auto const &v : rg[u])
f[ind[v]] = 1;
}
for (size_t i = 0; i < n; ++i)
w[i] = f[ind[i]] ^ (subtask == 4);
return w;
}
