#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second
#define vi vector<int>
#define all(x) x.begin(),x.end()
const int N = 5005;
int n, m, id[N];
vi ans;
vi g[N], R[N], t[N], t2[N];
bitset<N> vis, E[N];
vi ord, ch, tp;
vector<vi> C;
void dfs(int v){
vis[v] = 1;
for(int u: g[v]){
if(!vis[u]) dfs(u);
}
ord.pb(v);
}
void dfs2(int v){
vis[v] = 1;
C.back().pb(v);
for(int u: R[v]){
if(!vis[u]) dfs2(u);
}
}
void solv(int i){
// solve the i-th s
if(C[i].size() == 1){
// solve by itself I guess
int v = C[i][0];
if(tp[v] == 1){
ans[v] = 0;
for(int u: g[v]){
if(u==v && ch[v]){
ans[v] = 1;
break;
}
if(ans[u]){
ans[v] = 1;
break;
}
}
}else{
ans[v] = 0;
int tot = 0;
for(int u: g[v]){
if(u == v && ch[v] == 1){
tot++;
}else{
tot += ans[u];
}
}
if(tot == (int)g[v].size()){
ans[v] = 1;
}
}
return;
}
bool ok = 0;
vector<bool> res(n, -1);
for(int v: C[i]){
if(ch[v]){
ok = 1;
}
for(int u: g[v]){
if(id[u] != id[v]){
// that means u is processsed
if(tp[v] == ans[u]){
res[v] = ans[u];
}
}
}
}
// try to distribute fine's
for(int v: C[i]){
if(!ch[v]) continue;
vector<bool> fine(n, 0);
queue<int> q;
vi deg(n);
for(int u: C[i]){
if(tp[u]) deg[u] = 1;
else{
if(res[u] == 0) deg[u] = N + 5; // we cant really use this guy
else deg[u] = R[u].size();
}
}
bool ok = 0;
q.push(v);
while(!q.empty()){
int v = q.front();
q.pop();
for(int u: R[v]){
deg[u]--;
if(deg[u] == 0){
fine[u] = 1;
q.push(u);
}
}
}
if(fine[v]){
for(int u: C[i]){
if(fine[u] && res[u] == -1) res[u] = 1;
}
}
}
// now we got all res, don't we?
for(int u: C[i]) if(res[u] == -1) res[u] = 0;
for(int v: C[i]) ans[v] = res[v];
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
ch = r;
tp = a;
n = a.size();
m = u.size();
for(int i = 0; i < m; ++i){
g[u[i]].pb(v[i]);
R[v[i]].pb(u[i]);
}
for(int i = 0; i < n; ++i){
if(!vis[i]){
dfs(i);
}
}
reverse(all(ord));
vis = 0;
for(int v: ord){
if(!vis[v]){
C.pb(vi{});
dfs2(v);
for(int x: C.back()) id[x] = int(C.size())-1;
}
}
vi deg(n);
for(int i = 0; i < m; ++i){
if(id[u[i]] != id[v[i]]){
if(!E[id[u[i]]][id[v[i]]]){
t[id[u[i]]].pb(id[v[i]]);
t2[id[v[i]]].pb(id[u[i]]);
E[id[u[i]]][id[v[i]]] = 1;
deg[id[u[i]]]++;
}
}
}
ans.resize(n);
queue<int> q;
for(int i = 0; i < (int)C.size(); ++i) if(deg[i] == 0) q.push(i);
while(!q.empty()){
int x = q.front(); q.pop();
solv(x);
for(int y: t2[x]){
deg[y]--;
if(deg[y] == 0){
q.push(y);
}
}
}
return ans;
}
