#include "train.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int n, m, k;
vector<vector<int>> graph, graphr;
vector<bool> bl;
vector<int> order;
vector<int> cid;
vector<vector<int>> comp;
vector<bool> self_loop;
void dfs(int nd){
if(bl[nd]) return;
bl[nd] = 1;
for(int x: graph[nd]) dfs(x);
order.pb(nd);
}
void dfs2(int nd){
if(cid[nd] != -1) return;
cid[nd] = int(comp.size())-1;
comp.back().pb(nd);
for(int x: graphr[nd]) dfs2(x);
}
vector<vector<int>> scc;
vector<int> tsort;
void dfs3(int nd){
if(bl[nd]) return;
bl[nd] = 1;
for(int x: scc[nd]) dfs3(x);
tsort.pb(nd);
}
vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V){
n = A.size(), m = U.size();
graph.resize(n), graphr.resize(n);
bl.assign(n, 0);
cid.assign(n, -1);
self_loop.assign(n, 0);
for(int i = 0; i < m; i++){
if(U[i] == V[i]){
self_loop[U[i]] = 1;
continue;
}
graph[U[i]].pb(V[i]), graphr[V[i]].pb(U[i]);
}
for(int i = 0; i < n; i++) if(!bl[i]) dfs(i);
reverse(order.begin(), order.end());
for(int x: order) if(cid[x] == -1){
comp.pb({});
dfs2(x);
}
k = comp.size();
scc.resize(k);
set<pair<int,int>> scc_edges;
for(int i = 0; i < n; i++) for(int x: graph[i]) if(cid[x] != cid[i])
scc_edges.insert({cid[i], cid[x]});
for(auto [a, b]: scc_edges) scc[a].pb(b);
bl.assign(k, 0);
for(int i = 0; i < k; i++) if(!bl[i]) dfs3(i);
reverse(tsort.begin(), tsort.end());
vector<bool> charger(k, 0);
for(int _i = k-1, i = tsort[_i]; _i >= 0; _i--, i = tsort[_i]){
if(comp[i].size() == 1){
if(R[comp[i][0]] && self_loop[comp[i][0]]) charger[i] = 1;
}
else{
for(int x: comp[i]) if(R[x]) charger[i] = 1;
}
for(int x: scc[i]) charger[i] = charger[i]|charger[x];
}
vector<int> ans;
for(int i = 0; i < n; i++) ans.pb(charger[cid[i]]);
return ans;
}
