#include "train.h"
#include<bits/stdc++.h>
using namespace std;
const int TAILLEMAXI = 5002;
vector<int> adja[TAILLEMAXI];
int nbsommets, nbaretes;
vector<int> appartenance,recharge;
int dejavu[TAILLEMAXI];
int cycle[TAILLEMAXI];
int depart;
void dfs(int pos){
if (dejavu[pos]==1){
if (pos==depart){
cycle[depart] = 1;
}
return ;
}
dejavu[pos] = 1;
for (auto a:adja[pos]){
dfs(a);
}
}
int parcours(int pos){
if (dejavu[pos]!=-1){
return dejavu[pos];
}
dejavu[pos]=0;
if (cycle[pos]==1 and recharge[pos]==0){
dejavu[pos]=1;
}
for (auto a:adja[pos]){
dejavu[pos] = max(dejavu[pos], parcours(a));
}
return dejavu[pos];
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
appartenance = a;
recharge = r;
nbsommets = appartenance.size();
nbaretes = u.size();
for (int i=0;i<nbaretes;i++){
adja[u[i]].push_back(v[i]);
}
for (int i=0;i<nbsommets;i++){
for (int j=0;j<nbsommets;j++){
dejavu[j]=-1;
}
depart = i;
dfs(i);
}
vector<int> rep;
for (int i=0;i<nbsommets;i++){
for (int j=0;j<nbsommets;j++){
dejavu[j]=-1;
}
rep.push_back(parcours(i));
}
//cout<<dejavu[0]<<endl;
return rep;
}
