#include "train.h"
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ff first
#define ss second
#define ln "\n"
#define ld long double
vector<ll> are;
vector<ll> isc;
vector<pair<ll, ll>> edge;
vector<vector<ll>> A;
vector<vector<ll>> rA;
vector<vector<ll>> cA;
vector<ll> spec;
ll n, m;
void dfs1(ll u, vector<bool> &vis, vector<ll> &ord){
vis[u]=1;
for (auto i:A[u]){
ll v = edge[i].ff^edge[i].ss^u;
if (!vis[v]) dfs1(v, vis, ord);
}
ord.push_back(u);
}
void dfs2(ll u, vector<ll> &comp, ll cc){
comp[u]=cc;
if (isc[u]) spec[cc]=1;
for (auto i:rA[u]){
ll v = edge[i].ff^edge[i].ss^u;
if (comp[v]==-1) dfs2(v, comp, cc);
}
}
void dfs(ll u, vector<ll> &dp){
dp[u]=0;
for (auto v:cA[u]){
if (dp[v]==-1) dfs(v, dp);
dp[u]|=dp[v];
}
if (spec[u]) dp[u]=1;
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
n=a.size(); m=v.size();
isc=r; are=a;
cA.clear(); spec.clear();
rA.clear(); rA.resize(n);
A.clear(); A.resize(n);
edge.clear(); edge.resize(m);
for (ll i=0; i<m; i++){
edge[i] = {u[i], v[i]};
A[u[i]].push_back(i);
rA[v[i]].push_back(i);
}
vector<bool> vis(n);
vector<ll> ord;
for (ll i=0; i<n; i++){
if (!vis[i]){
dfs1(i, vis, ord);
}
}
reverse(ord.begin(), ord.end());
vector<ll> comp(n, -1);
ll cc=0;
for (auto i:ord){
if (comp[i]==-1){
spec.push_back(0);
dfs2(i, comp, cc++);
}
}
cA.resize(cc);
for (ll i=0; i<m; i++){
if (comp[edge[i].ff]!=comp[edge[i].ss]) cA[comp[edge[i].ff]].push_back(comp[edge[i].ss]);
}
vector<ll> dp(cc, -1);
for (ll i=0; i<cc; i++){
if (dp[i]==-1) dfs(i, dp);
}
vector<ll> ans(n);
for (ll i=0; i<n; i++){
ans[i]=dp[comp[i]];
}
return ans;
}
