#include "train.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const int MAXN = 1e6 + 10;
int n, m, col[MAXN], c;
bool A[MAXN], R[MAXN];
vector<int> adj[MAXN], adj_r[MAXN];
bool W[MAXN], in_edge[MAXN], WC[MAXN];
vector<int> ord;
void dfs(int v) {
col[v] = 1;
for (int u : adj[v])
if (!col[u])
dfs(u);
ord.push_back(v);
}
void sfd(int v) {
col[v] = c;
for (int u : adj_r[v])
if (!col[u])
sfd(u);
}
vector<int> who_wins(vector<int> a_, vector<int> r_, vector<int> u_, vector<int> v_) {
n = a_.size();
for (int i = 0; i < n; i++)
A[i] = a_[i], R[i] = r_[i];
m = u_.size();
for (int i = 0; i < m; i++)
adj[u_[i]].push_back(v_[i]), adj_r[v_[i]].push_back(u_[i]);
for (int i = 0; i < n; i++)
if (!col[i])
dfs(i);
memset(col, 0, sizeof col);
reverse(all(ord));
for (int e : ord) {
if (!col[e]) {
c++;
sfd(e);
}
}
for (int u = 0; u < n; u++)
for (int v : adj[u])
if (col[u] == col[v])
in_edge[col[u]] = true;
for (int u = 0; u < n; u++)
if (in_edge[col[u]] && R[u])
WC[col[u]] = true;
for (int i = 0; i < n; i++)
for (int v = 0; v < n; v++)
for (int u : adj[v])
WC[col[v]] |= WC[col[u]];
vector<int> res;
for (int i = 0; i < n; i++)
res.push_back(WC[col[i]]);
return res;
}
