#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){
// cout << "COMP: ";
// for(auto u: COMP){
// cout << u << " ";
// }
// cout << "\n";
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[A] == 1 && r[A] == 0) && (a[B] == 1 && r[B] == 0) && to_in[A] == to_in[B]){ //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];
bool forced[mx];
int cur_deg[mx]; //number of neighbors that can be forced into a good C
int bad_cur_deg[mx];
int self[mx];
queue<int> to_unForce;
void iForce(int node){
for(auto u: radj[node]){
if(forced[u]) continue;
if(a[u] == 0){
cur_deg[u]++;
//cout << u << " " << cur_deg[u] << "\n";
if(cur_deg[u] == sz(adj[u])-self[u]){
forced[u] = 1;
to_unForce.push(u);
}
}
else{
forced[u] = 1;
to_unForce.push(u);
}
}
}
void initForce(){
for(int i = 0; i < n; i++){
if(r[i] == 1){
if(!forced[i]){
forced[i] = 1;
to_unForce.push(i);
}
}
}
while(sz(to_unForce)){
int node = to_unForce.front();
to_unForce.pop();
iForce(node);
}
for(int i = 0; i < n; i++){
if(forced[i]){
cur_deg[i] = 0;
for(auto u: adj[i]){
if(forced[u]){
cur_deg[i]++;
}
}
}
}
}
queue<int> q;
void unForce(int node){
assert(forced[node] == 0);
//cout << "unForce " << node << "\n";
for(auto u: radj[node]){
if(forced[u]){
if(a[u] == 1){
cur_deg[u]--;
if(cur_deg[u] == 0 || (self[u] == cur_deg[u] && r[u] == 0)){
forced[u] = 0;
to_unForce.push(u);
if(!bad[u] && a[u] == 1){ //second condition unnecessary
bad[u] = 1;
q.push(u);
}
}
}
else{
forced[u] = 0;
to_unForce.push(u);
}
}
}
}
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]);
}
for(int i = 0; i < n; i++){
for(auto u: adj[i]){
if(u == i){
self[i]++;
}
}
}
initForce();
//cout << "cur_deg[2]: " << cur_deg[2] << "\n";
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++){
// cout << i << " " << forced[i] << " " << cur_deg[i] << "\n";
// }
for(int i = 0; i < n; i++){
bad_cur_deg[i] = sz(adj[i]);
if(dp[i] == 1){
q.push(i);
bad[i] = 1;
//cout << "initial bad: " << i << "\n";
}
}
for(int i = 0; i < n; i++){
if(!forced[i] && !bad[i] && a[i] == 1){ //second condition unnecessary
q.push(i);
bad[i] = 1;
//cout << i << "\n";
}
}
while(true){
while(sz(to_unForce)){
int node = to_unForce.front();
to_unForce.pop();
unForce(node);
}
if(sz(q) == 0) break;
int node = q.front();
q.pop();
for(auto u: radj[node]){
if(bad[u]) continue;
if(a[u] == 1){
bad_cur_deg[u]--;
if(bad_cur_deg[u] == 0){
bad[u] = 1;
q.push(u);
}
}
else{
bad[u] = 1;
q.push(u);
}
}
if(forced[node]){
forced[node] = 0;
to_unForce.push(node);
}
}
vi ans(n, 0);
for(int i = 0; i < n; i++){
if(!bad[i]){
ans[i] = 1;
}
}
return ans;
}
