#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
const int MAXN=5e3+10;
const ll inf=1e16;
typedef pair<int,int> pii;
int n,id[MAXN],mn[MAXN],cur,pai[MAXN],grau[MAXN],gr2[MAXN];
vector<int> a,dp;
vector<int> g[MAXN],g2[MAXN],rev[MAXN];
bool inst[MAXN],z[MAXN],mark[MAXN],has[MAXN];
stack<int> st;
void dfs(int x){
id[x]=mn[x]=++cur;
z[x]=1;
inst[x]=1;
st.push(x);
for(auto u:g[x]){
if(!z[u]){
dfs(u);
mn[x]=min(mn[x],mn[u]);
}
else if(inst[u]) mn[x]=min(mn[x],mn[u]);
}
if(mn[x]==id[x]){
int v;
do{
v=st.top(); st.pop();
pai[v]=x;
inst[v]=0;
}while(v!=x);
}
}
void solve(vector<int> v,int val){
queue<int> fila;
for(auto x:v){
for(auto u:g[x]){
if(u==x && mark[x]==a[x]){
dp[x]=a[x];
has[x]=1;
fila.push(x);
break;
}
if(pai[u]==pai[x]) continue;
if(dp[u]==a[x]){
has[x]=1;
dp[x]=a[x];
fila.push(x);
break;
}
}
if(!has[x] && !gr2[x]){
dp[x]=(a[x]^1);
fila.push(x);
has[x]=1;
}
}
while(!fila.empty()){
auto x=fila.front(); fila.pop();
for(auto u:rev[x]){
if(has[u]) continue;
if(a[u]==dp[x]){
has[u]=1;
fila.push(u);
dp[u]=dp[x];
continue;
}
gr2[u]--;
if(!gr2[u]){
fila.push(u);
dp[u]=(a[u]^1);
has[u]=1;
}
}
}
for(auto x:v) if(!has[x]) dp[x]=val;
}
std::vector<int> who_wins(std::vector<int> A, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
a=A;
n=sz(a);
dp.resize(n);
fall(i,0,sz(u)-1) g[u[i]].pb(v[i]);
fall(i,0,n-1) if(!id[i]) dfs(i);
fall(i,0,n-1){
mark[i]=r[i];
int x=pai[i];
for(auto u:g[x]){
u=pai[u];
if(u==x){
rev[u].pb(x);
gr2[x]++;
continue;
}
grau[x]++;
g2[u].pb(x);
}
}
queue<int> fila;
fall(i,0,n-1) if(pai[i]==i && !grau[i]) fila.push(i);
while(!fila.empty()){
auto x=fila.front(); fila.pop();
bool isg=0;
vector<int> v;
fall(i,0,n-1)
if(pai[i]==x){
v.pb(i);
isg|=mark[i];
}
if(!isg) solve(v,0);
else solve(v,1);
for(auto u:g2[x]){
grau[u]--;
if(!grau[u]) fila.push(u);
}
}
return dp;
}
