#include <cstdio>
#include <vector>
#include <cassert>
#include "train.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
void debug(vi v){
for (int x:v) cerr << x << ' ';
cerr<<'\n';
}
bool escaso1(vector<int> who){
for (int x:who){
if (x==0) return 0;
}
return 1;
}
bool escaso2(vector<int> who){
for (int x:who){
if (x==1) return 0;
}
return 1;
}
vi caso_todos1(vector<int> who, vector<int> charge, vector<int> u, vector<int> v){
int n=who.size();
int m=u.size();
vi sol(n);
vvi conexiones(n);
for (int i=0;i<m;i++){
conexiones[u[i]].push_back(v[i]);
}
vector<bool> charging(n,false);
vector<int> chargin;
for (int i=0;i<n;i++){
if (charge[i]) chargin.push_back(i);
}
//cerr<<0;
for (int x:chargin){
vector<bool> porvisitar(n,true);
queue<int> cola;
cola.push(x);
bool T=true;
while (cola.size()){
//cerr<<1;
int ac=cola.front();
//cerr<< ' ' << ac << ' ' <<cola.size()<<'\n';
//cerr<<2;
cola.pop();
//cerr<<3;
if (porvisitar[ac]){
//cerr<<4;
porvisitar[ac]=false;
//cerr<<5;
for (int y:conexiones[ac]) cola.push(y);
//cerr<<6;
}
else if (ac==x) T=false;
}
//cerr<<7;
if (not T) charging[x]=true;
}
//cerr<<1;
for (int x=0;x<n;x++){
vector<bool> porvisitar(n,true);
queue<int> cola;
cola.push(x);
bool T=true;
while (cola.size() and T){
int ac=cola.front();
cola.pop();
if (porvisitar[ac]){
if(charging[ac]){
T=false;
break;
}
porvisitar[ac]=false;
for (int y:conexiones[ac]) cola.push(y);
}
}
if (T){
sol[x]=0;
}
else sol[x]=1;
}
return sol;
}
vi caso_todos2(vector<int> who, vector<int> charge, vector<int> u, vector<int> v){
int n=who.size();
int m=u.size();
vi sol(n);
vvi conexiones(n);
for (int i=0;i<m;i++){
conexiones[u[i]].push_back(v[i]);
}
vector<bool> charging(n,false);
vector<int> chargin;
for (int i=0;i<n;i++){
if (charge[i]) chargin.push_back(i);
}
//cerr<<0;
for (int x=0;x<n;x++){
vector<int> porvisitar=charge;
for (int i=0;i<n;i++) porvisitar[i]=-porvisitar[i]+1;
queue<int> cola;
cola.push(x);
bool T=true;
while (cola.size()){
//cerr<<1;
int ac=cola.front();
//cerr<< ' ' << ac << ' ' <<cola.size()<<'\n';
//cerr<<2;
cola.pop();
//cerr<<3;
if (porvisitar[ac]){
//cerr<<4;
porvisitar[ac]=false;
//cerr<<5;
for (int y:conexiones[ac]) cola.push(y);
//cerr<<6;
}
else if (ac==x) T=false;
}
//cerr<<7;
if (charge[x]) T=true;
if (not T) charging[x]=true;
}
//cerr<<1;
for (int x=0;x<n;x++){
vector<bool> porvisitar(n,true);
queue<int> cola;
cola.push(x);
bool T=true;
while (cola.size() and T){
int ac=cola.front();
cola.pop();
if (porvisitar[ac]){
if(charging[ac]){
T=false;
break;
}
porvisitar[ac]=false;
for (int y:conexiones[ac]) cola.push(y);
}
}
if (T){
sol[x]=0;
}
else sol[x]=1;
}
return sol;
}
vector<int> who_wins(vector<int> who, vector<int> charge, vector<int> u, vector<int> v) {
if (escaso1(who)) return caso_todos1(who,charge,u,v);
else if (escaso2(who)) return caso_todos2(who,charge,u,v);
return vi(0);
}
