#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,S=1.5e7;
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],g[N];
int dp[18][S];
int w[18];
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;
}
if(count(rg(a),0)==0) {
for(int i=0; i<m; ++i) e[u[i]].push_back(v[i]);
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=1; i<=scnt; ++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;
}
if(count(rg(a),1)==0) {
for(int i=0; i<m; ++i) if(r[u[i]]+r[v[i]]==0) e[u[i]].push_back(v[i]);
for(int i=0; i<n; ++i) if(!r[i]&&!dfn[i]) tarjan(i);
for(int i=0; i<n; ++i) if(!r[i]) {
for(auto j : e[i]) if(scc[i]==scc[j]) bz[scc[i]]|=1;
}
for(int i=0; i<n; ++i) g[i]=bz[scc[i]];
for(int i=0; i<m; ++i) if(r[u[i]]+r[v[i]]!=0) e[u[i]].push_back(v[i]);
memset(dfn,0,sizeof(dfn));
scnt=dfc=0;
for(int i=0; i<n; ++i) if(!dfn[i]) tarjan(i);
for(int i=0; i<n; ++i)
for(auto j : e[i])
if(scc[i]!=scc[j])
ee[scc[i]].push_back(scc[j]);
for(int i=0; i<n; ++i) f[scc[i]]|=g[i];
for(int i=1; i<=scnt; ++i) 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;
}
if(n<=15) {
for(int i=0; i<m; ++i) e[u[i]].push_back(v[i]);
memset(dp,-1,sizeof(dp));
const auto hash=[&](const vector<int> &a) {
int x=0;
for(auto i : a) x=x*3+i;
return x;
};
function<int(vector<int>,int)> dfs=[&](vector<int> s,int u) -> int {
int h=hash(s);
if(dp[u][h]!=-1) return dp[u][h];
for(auto v : e[u]) {
if(s[v]==2&&a[u]==1) return dp[u][h]=1;
if(s[v]==1&&a[u]==0) return dp[u][h]=0;
if(s[v]==0) {
vector<int> t=s;
t[v]=1;
if(r[v]) for(auto &i : t) if(i==1) i=2;
if(dfs(t,v)==a[u]) return dp[u][h]=a[u];
}
}
return dp[u][h]=a[u]^1;
};
vector<int> ans(n);
for(int i=0; i<n; ++i) {
vector<int> x(n);
x[i]=r[i]+1;
ans[i]=dfs(x,i);
}
return ans;
}
return {};
}
