#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], res[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
// for(int x: C[i]) cerr << x << ' ';
// cerr << "\n\n";
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;
}
for(int j = 0; j < n; ++j) res[j] = -1;
queue<int> q;
for(int v: C[i]){
for(int u: g[v]){
if(u == v){
if(tp[u] == 0){
if(ch[u] == 0) res[v] = 0;
}else{
if(ch[v]){
res[v] = 1;
}
}
}
if(id[u] != id[v]){
// that means u is processsed
if(tp[v] == ans[u]){
// cerr << v << ' ' << ans[u] << ' ' << u << " crap\n";
res[v] = ans[u];
}
}
}
if(res[v] == 1) q.push(v);
}
// for(int v: C[i]){
// if(ch[v] == 0 && res[v] != 1) continue;
// q.push(v);
// if(res[v] == 1) fine[v] = 1;
// }
vi deg(n);
for(int u: C[i]){
if(tp[u]) deg[u] = 1;
else{
if(res[u] == 0) deg[u] = 1000000; // we cant really use this guy
else{
deg[u] = g[u].size();
for(int x: g[u]) if(id[x] != id[u]) --deg[u];
}
}
}
while(!q.empty()){
int v = q.front();
q.pop();
for(int u: R[v]){
deg[u]--;
if(deg[u] == 0){
res[u] = 1;
q.push(u);
}
}
}
// we distributed the lower nodes result I guess
// now we need to use the chargers..
for(int v: C[i]){
if(ch[v] && res[v] != 0){
// we gotta apply this guy
deg.clear();
deg.resize(n, 0);
vector<int> fine(n, -1);
q.push(v);
for(int u: C[i]){
if(tp[u]) deg[u] = 1;
else{
if(res[u] == 0) deg[u] = 1000000; // we cant really use this guy
else{
deg[u] = g[u].size();
for(int x: g[u]){
if(id[x] != id[u]) --deg[u];
else if(res[x] == 1) --deg[u];
}
if(deg[u] == 0) deg[u] = 1;
}
}
}
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] == 1){
for(int u: C[i]) if(fine[u]) 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;
// for(int x: C.back()) cerr << x << ' ';
// cerr << '\n';
}
}
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;
}
