#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
const int MOD = 1e9+7;
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define bk back()
#define all(x) begin(x), end(x)
const int mx = 5005;
int n, m;
vi a, r, u, v;
vi adj[mx];
vi radj[mx];
int to_in[mx];
int to_out[mx];
bool visited[mx];
vi order;
void dfs1(int node){
if(a[node] == 0 || r[node] == 1) return;
for(auto u: adj[node]){
if(!visited[u]){
visited[u] = 1;
dfs1(u);
}
}
order.pb(node);
}
vector<vi> comps;
vi comp;
void dfs2(int node){
if(a[node] == 0 || r[node] == 1) return;
comp.pb(node);
for(auto u: radj[node]){
if(!visited[u]){
visited[u] = 1;
dfs2(u);
}
}
}
void reduceAStrong(){
//create new adj, remove self edges for AN
for(int i = 0; i < n; i++){
visited[i] = 0;
}
for(int i = 0; i < n; i++){
if(!visited[i]){
visited[i] = 1;
dfs1(i);
}
}
for(int i = 0; i < n; i++){
visited[i] = 0;
}
reverse(all(order));
for(auto u: order){
if(!visited[u]){
comp.clear();
visited[u] = 1;
dfs2(u);
comps.pb(comp);
}
}
for(int i = 0; i < n; i++){
adj[i].clear();
radj[i].clear();
}
for(auto COMP: comps){
for(int i = 0; i < sz(COMP); i++){
to_in[COMP[i]] = COMP[0];
to_out[COMP[i]] = COMP.bk;
if(i+1 < sz(COMP)){
adj[COMP[i]].pb(COMP[i+1]);
}
}
}
for(int i = 0; i < m; i++){
int A = u[i];
int B = v[i];
if(a[A] == 1 && r[A] == 0){
A = to_out[A];
}
if(a[B] == 1 && r[B] == 0){
B = to_in[B];
}
if(A == B && (a[A] == 1 && r[A] == 0)){ //remove self edge
continue;
}
adj[A].pb(B);
}
for(int i = 0; i < n; i++){
for(auto u: adj[i]){
radj[u].pb(i);
}
}
}
array<bool, mx> dp;
array<bool, mx> ndp;
bool bad[mx];
int cur_deg[mx]; //for A
vi who_wins(vi _a, vi _r, vi _u, vi _v) {
a = _a;
r = _r;
u = _u;
v = _v;
n = sz(a);
m = sz(u);
for(int i = 0; i < m; i++){
adj[u[i]].pb(v[i]);
radj[v[i]].pb(u[i]);
}
reduceAStrong();
queue<int> q;
for(int i = 0; i < n; i++){
dp[i] = 1;
if(r[i] == 1) dp[i] = 0;
}
for(int rep = 0; rep < mx; rep++){
for(int i = 0; i < n; i++){
ndp[i] = 0;
}
for(int i = 0; i < n; i++){
if(r[i] == 1) continue;
if(a[i] == 1){
ndp[i] = 1;
for(auto u: adj[i]){
if(dp[u] == 0) ndp[i] = 0;
}
}
else{
ndp[i] = 0;
for(auto u: adj[i]){
if(dp[u] == 1) ndp[i] = 1;
}
}
}
swap(dp, ndp);
}
for(int i = 0; i < n; i++){
cur_deg[i] = sz(adj[i]);
if(dp[i] == 1){
q.push(i);
bad[i] = 1;
}
}
while(sz(q)){
int node = q.front();
q.pop();
for(auto u: radj[node]){
if(bad[u]) continue;
if(a[u] == 1){
cur_deg[u]--;
if(cur_deg[u] == 0){
bad[u] = 1;
q.push(u);
}
}
else{
bad[u] = 1;
q.push(u);
}
}
}
vi ans(n, 0);
for(int i = 0; i < n; i++){
if(!bad[i]){
ans[i] = 1;
}
}
return ans;
}
