#include <bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define vvb vector<vb>
#define ii pair<int, int>
#define x first
#define y second
#define vii vector<ii>
#define pb push_back
#define all(x) x.begin(), x.end()
#define loop(i,s,e) for(int i=s;i<e;++i)
#define loopr(i,s,e) for(int i=e-1;i>=s;--i)
#define chkmin(a,b) a = min(a,b)
#define chkmax(a,b) a = max(a,b)
using namespace std;
const int INF = 1e9;
int n;
vb check;
void dfs(int cur, vi& vec, vvi& g){
if (check[cur]) return ;
check[cur] = 1;
for(auto nei:g[cur]) dfs(nei, vec, g);
vec.pb(cur);
}
vvi g, ag;
vi solvesmall(vi& a, vi& r){
return vi(n,0);
}
vi who_wins(vi a, vi r, vi u, vi v) {
n = a.size();
g.resize(n); ag.resize(n); check.resize(n);
loop(i,0,u.size()){
int a = u[i], b = v[i];
g[a].pb(b);
ag[b].pb(a);
}
vi res(n);
//if (n<=15) return solvesmall(a,r);
bool same = 1;
loop(i,1,n) if(a[i]!=a[0]) same = 0;
if (!same){
res[n-1] = r[n-1];
loopr(i,0,n-1){
int tmp = -1;
res[i] = r[i];
for(auto nei:g[i]){
if (nei==i){
if ((a[i] ^ r[i]) == 0) tmp = r[i];
}
else res[i] = res[nei];
}
if (tmp!=-1) res[i] = tmp;
}
return res;
}
if (a[0]){
vi order;
loop(i,0,n) dfs(i, order, ag);
reverse(all(order));
fill(all(check),0);
for(auto cur:order){
if (check[cur]) continue;
vi vec;
dfs(cur, vec, g);
/*for(auto i:vec) cout<<i<<" ";
cout<<endl;*/
bool good = 0;
for(auto i:vec) if (r[i]) good = 1;
if (vec.size()==1){
bool self = 0;
for(auto nei:g[vec[0]]) if (nei==vec[0]) self = 1;
if (!self) good = 0;
}
if (!good){
for(auto c:vec) for(auto nei:g[c]){
if (res[nei]) good = 1;
}
}
for(auto i:vec) res[i] = good;
}
}
else{
loop(i,0,n) check[i]=r[i];
vi order;
loop(i,0,n) dfs(i, order, ag);
reverse(all(order));
loop(i,0,n) check[i]=r[i];
for(auto cur:order){
if (check[cur]) continue;
vi vec;
dfs(cur, vec, g);
bool good = 1;
if (vec.size()==1){
good = 0;
for(auto nei:g[vec[0]]) if (nei==vec[0]) good = 1;
}
for(auto i:vec) res[i] = good;
}
order.clear();
fill(all(check),0);
loop(i,0,n) dfs(i, order, ag);
reverse(all(order));
fill(all(check),0);
for(auto cur:order){
if (check[cur]) continue;
vi vec;
dfs(cur, vec, g);
/*for(auto i:vec) cout<<i<<" ";
cout<<endl;*/
bool good = 0;
for(auto i:vec){
if (res[i]) good = 1;
else for(auto nei:g[i]) if(res[nei]) good = 1;
}
for(auto i:vec) res[i] = good;
}
loop(i,0,n) res[i] = !res[i];
}
return res;
}
/*
clear
g++ c.cpp grader.cpp -o c ; ./c
6 7
0 0 0 0 0 0
1 0 0 0 0 1
0 1
1 2
2 3
3 1
4 5
5 5
4 1
*/
