#include <bits/stdc++.h>
using namespace std;
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
int n = a.size();
int m = u.size();
vector<vector<int>> adj(n), radj(n);
for(int i=0;i<m;i++){
adj[u[i]].push_back(v[i]);
radj[v[i]].push_back(u[i]);
}
// 1) find SCC with Tarjan
vector<int> disc(n,-1), low(n), comp(n), st;
vector<bool> inst(n,false);
int timer=0, scc_count=0;
function<void(int)> dfs = [&](int x){
disc[x]=low[x]=timer++;
st.push_back(x);
inst[x]=true;
for(int y:adj[x]){
if(disc[y]<0){
dfs(y);
low[x]=min(low[x],low[y]);
}else if(inst[y]){
low[x]=min(low[x],disc[y]);
}
}
if(low[x]==disc[x]){
while(true){
int w=st.back(); st.pop_back();
inst[w]=false;
comp[w]=scc_count;
if(w==x) break;
}
scc_count++;
}
};
for(int i=0;i<n;i++)
if(disc[i]<0) dfs(i);
// 2) condensed graph edges + charge info
vector<vector<int>> cadj(scc_count);
vector<int> charge_scc(scc_count,0);
for(int i=0;i<n;i++)
if(r[i]) charge_scc[comp[i]]=1;
for(int i=0;i<m;i++){
int cu=comp[u[i]], cv=comp[v[i]];
if(cu!=cv) cadj[cu].push_back(cv);
}
// 3) Build full graph of states, not SCC-level
// win[i] = -1 unknown, 0 lose, 1 win
vector<int> win(n,-1), outdeg(n);
for(int i=0;i<n;i++)
outdeg[i] = adj[i].size();
queue<int> q;
// Any node in SCC with charge is winning (cycle with recharge)
for(int i=0;i<n;i++){
if(charge_scc[comp[i]]){
win[i]=1;
q.push(i);
}
}
// 4) backward game propagation
while(!q.empty()){
int x=q.front(); q.pop();
for(int p:radj[x]){
if(win[p]!=-1) continue;
if(a[p]==1){
// p belongs to Arezou
// If she can point to a winning, p is winning
win[p]=1;
q.push(p);
}else{
// p belongs to Borzou
// remove x from safe choices
outdeg[p]--;
if(outdeg[p]==0){
// all moves lead to winners => p is losing (Borzou can't force a lose)
win[p]=0;
q.push(p);
}
}
}
}
// Remaining unknown:
// For any node still -1:
// - If Arezou node: all outgoing lead to nodes not confirmed winning => losing
// - If Borzou node: there exists some outgoing not winning => winning
for(int i=0;i<n;i++){
if(win[i]!=-1) continue;
if(a[i]==1){
// Arezou: if there's at least one edge to a non-losing, but unknown = losing
bool canWin=false;
for(int nx:adj[i])
if(win[nx]==1) canWin=true;
win[i]= canWin?1:0;
} else {
// Borzou: if there's at least one edge to a losing
bool canLose=false;
for(int nx:adj[i])
if(win[nx]==0) canLose=true;
win[i]= canLose?0:1;
}
}
vector<int> ans(n);
for(int i=0;i<n;i++)
ans[i] = (win[i]==1?1:0);
return ans;
}
