#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
void ckmin(pi& a, pi b){
a = min(a, b);
}
void ckmax(pi& a, pi b){
a = max(a, b);
}
const int mx = 5005;
int n, m;
vi a, r, u, v;
vi adj[mx];
array<pi, mx> dp;
array<pi, mx> ndp;
int trans_ans[mx];
vi cur_ans;
void genCurAns(int node){
assert(trans_ans[node] != -1);
assert(cur_ans[node] > 1);
// cout << "node: " << node << "\n";
// for(int i = 0; i < n; i++){
// cout << "cur_ans[" << i << "]: " << cur_ans[i] << "\n";
// }
if(cur_ans[trans_ans[node]] <= 1){
cur_ans[node] = cur_ans[trans_ans[node]];
return;
}
cur_ans[node] = 3;
if(cur_ans[trans_ans[node]] == 2){
genCurAns(trans_ans[node]);
cur_ans[node] = cur_ans[trans_ans[node]];
return;
}
else{
assert(cur_ans[trans_ans[node]] == 3);
int sum = r[node];
int cur_node = trans_ans[node];
while(cur_node != node){
sum+=r[cur_node];
cur_node = trans_ans[cur_node];
}
if(sum >= 1){
cur_ans[node] = 1;
}
else{
cur_ans[node] = 0;
}
return;
}
}
vi getAnsFromTrans(){
cur_ans = vi(n, 2);
for(int i = 0; i < n; i++){
if(cur_ans[i] == 2){
genCurAns(i);
}
}
return cur_ans;
}
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]);
}
for(int i = 0; i < n; i++){
dp[i] = mp(0, -1);
}
int REP = 10005;
for(int rep = 0; rep < REP; rep++){
for(int i = 0; i < n; i++){
if(a[i]){
ndp[i] = mp(-MOD, -1);
}
else{
ndp[i] = mp(MOD, -1);
}
}
for(int i = 0; i < n; i++){
if(a[i]){
for(int& u: adj[i]){
ckmax(ndp[i], mp(dp[u].f, u));
}
}
else{
for(int& u: adj[i]){
ckmin(ndp[i], mp(dp[u].f, u));
}
}
if(r[i]){
ndp[i].f++;
}
}
swap(dp, ndp);
}
vi ans(n, 0);
for(int i = 0; i < n; i++){
if(dp[i].f > (REP/(n+1))){
ans[i] = 1;
}
}
return ans;
for(int i = 0; i < n; i++){
cout << i << " " << dp[i].f << " " << dp[i].s << "\n";
}
for(int i = 0; i < n; i++){
trans_ans[i] = dp[i].s;
cout << "i, trans[i]: " << i << " " << trans_ans[i] << "\n";
assert(trans_ans[i] != -1);
}
return getAnsFromTrans();
}
