#include<bits/stdc++.h>
#include "train.h"
using namespace std;
const int MAX_SOM=5000+5;
int nbSom,nbAre,nbCompo;
vector<int> rep,possed,charg,ordre;
vector<int> adjaTrans[MAX_SOM],adja[MAX_SOM],listeCompo[MAX_SOM];
int compo[MAX_SOM],dv[MAX_SOM],cycle[MAX_SOM];
void DFS(int pos) {
if (dv[pos]==0) {
dv[pos]=1;
for (int i:adja[pos]) {
DFS(i);
}
ordre.push_back(pos);
}
}
void DFS2(int pos) {
if (compo[pos]==0) {
compo[pos]=nbCompo;
listeCompo[nbCompo].push_back(pos);
for (int i:adjaTrans[pos]) {
DFS2(i);
}
}
}
void remonte(int pos) {
if (rep[pos]==0) {
rep[pos]=1;
for (int i:adjaTrans[pos]) {
remonte(i);
}
}
}
vector<int> who_wins(vector<int> a,vector<int> r,vector<int> u,vector<int> v) {
nbSom=a.size();
nbAre=u.size();
possed=a;
charg=r;
rep.resize(nbSom,0);
for (int i=0;i<nbAre;i++) {
if (u[i]==v[i]) {
cycle[u[i]]=1;
}
adja[u[i]].push_back(v[i]);
adjaTrans[v[i]].push_back(u[i]);
}
for (int i=0;i<nbSom;i++) {
DFS(i);
}
reverse(ordre.begin(),ordre.end());
for (int i:ordre) {
if (compo[i]==0) {
nbCompo++;
DFS2(i);
}
}
int presCharg;
for (int i=1;i<=nbCompo;i++) {
presCharg=0;
for (int j:listeCompo[i]) {
if (charg[j]==1) {
presCharg=1;
}
//cout<<j<<" ";
}
//cout<<endl;
if (presCharg==1 and ((int)listeCompo[i].size()>1 or cycle[listeCompo[i][0]]==1)) {
remonte(listeCompo[i][0]);
}
}
return rep;
}
