#include "train.h"
#include <bits/stdc++.h>
#define rg(x) (x).begin(),(x).end()
using namespace std;
using vi=vector<int>;
const int N=5005;
int n,m;
vi e[N],ee[N];
int d[N];
int dfn[N],low[N],dfc;
int stk[N],tp,scc[N],scnt;
bool instk[N];
int bz[N],f[N];
void tarjan(int u) {
dfn[u]=low[u]=++dfc;
instk[u]=1;
stk[++tp]=u;
for(auto v : e[u])
if(!dfn[v]) {
tarjan(v);
low[u]=min(low[u],low[v]);
} else if(instk[v])
low[u]=min(low[u],dfn[v]);
if(low[u]==dfn[u]) {
++scnt;
do instk[stk[tp]]=0,scc[stk[tp]]=scnt; while(stk[tp--]!=u);
}
}
vi who_wins(vi a,vi r,vi u,vi v) {
n=a.size(),m=u.size();
const auto check1=[&]() {
for(int i=0; i<m; ++i) if(u[i]!=v[i]&&u[i]+1!=v[i]) return 0;
return 1;
};
if(check1()) {
for(int i=0; i<m; ++i) if(u[i]==v[i]) bz[u[i]]|=1; else bz[u[i]]|=2;
vi ans(n,0);
for(int i=n-1; i>=0; --i) {
if((a[i]==r[i]&&(bz[i]&1))||(~bz[i]&2)) ans[i]=r[i];
else ans[i]=ans[i+1];
}
return ans;
}
for(int i=0; i<m; ++i) e[u[i]].push_back(v[i]);
if(count(rg(a),0)==0) {
for(int i=0; i<n; ++i) if(!dfn[i]) tarjan(i);
for(int i=0; i<n; ++i) {
bz[scc[i]]|=r[i];
for(auto j : e[i]) if(scc[i]==scc[j]) bz[scc[i]]|=2; else ee[scc[i]].push_back(scc[j]);
}
for(int i=scnt; i>=1; --i) {
f[i]=bz[i]==3;
for(auto j : ee[i]) f[i]|=f[j];
}
vector<int> ans(n);
for(int i=0; i<n; ++i) ans[i]=f[scc[i]];
return ans;
}
return {};
}
