#include "train.h"
#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define ll long long
#define ff first
#define ss second
#define pii pair<int,int>
#define mk make_pair
#define lp(i,a,b) for(int i = a ; i< b ; i++)
const int MAXN = 5010 ;
using namespace std;
int N , M ;
bool is_a[MAXN] , is_charger[MAXN] ;
vector<int> good_for_a , good_for_b ;
bool marc[MAXN] ;
vector<int> adj[MAXN] , revAdj[MAXN] ;
vector<int> List ;
vector< vector<int> > components ;
int deg[MAXN] ;
void dfs1(int x)
{
marc[x] = true ;
for(auto e : adj[x] )
if(!marc[e] ) dfs1(e) ;
List.push_back(x) ;
}
void dfs2(int x)
{
marc[x] = true ;
components.back().pb(x) ;
for(auto e : revAdj[x])
if(!marc[e]) dfs2(e) ;
}
void goUpwards(vector<int> v)
{
int ini = 0 ;
while(ini < sz(v) )
{
int x = v[ini++] ;
for(auto e : revAdj[x])
{
bool k = good_for_a[e]|good_for_b[e] ;
if(!k && is_a[e] == good_for_a[x] )
{
if(is_a[e]) good_for_a[e] = true ;
else good_for_b[e] = true ;
v.pb(e) ;
}
else if(!k && sz(adj[e]) == 1 )
{
if(is_a[e]) good_for_b[e] = true ;
else good_for_a[e] = true ;
v.pb(e) ;
}
for(int i = 0 ; i < sz(adj[e]) ; i++ )
{
if( adj[e][i] != x ) continue ;
swap(adj[e][i] , adj[e].back() ) ;
adj[e].pop_back() ;
break ;
}
}
revAdj[x].clear() ;
for(auto e : adj[x] )
for(int i= 0 ; i < sz(revAdj[e]) ; i++ )
{
if( revAdj[e][i] != x ) continue ;
swap(revAdj[e][i] , revAdj[e].back() ) ;
revAdj[e].pop_back() ;
break ;
}
adj[x].clear() ;
}
// for(auto e : v ) cout << e <<" " << good_for_a[e] << endl ;
}
bool solve()
{
components.clear() ;
List.clear() ;
for(int i = 0 ; i < N ; i++ ) marc[i] = good_for_a[i]|good_for_b[i] ;
for(int i = 0 ; i < N ; i++ )
{
if(marc[i]) continue ;
deg[i] = 0 ;
for(int j : adj[i] )
if( !marc[j] ) deg[i]++ ;
if(is_a[i]) deg[i] = 1 ;
}
for(int i = 0 ; i < N ; i++ )
if(!marc[i]) dfs1(i) ;
if( List.empty() ) return false ;
for(int i : List ) marc[i] = false ;
for(int i = sz(List)-1 ; i >= 0 ; i-- )
{
if(marc[List[i]]) continue ;
components.push_back(vector<int>()) ;
dfs2(List[i]) ;
}
for(int i : List ) marc[i] = false ;
for(int i = 0 ; i < sz(components)-1 ; i++ )
for(auto e : components[i] ) marc[e] = true ;
for(auto e : components.back() )
{
if( !is_charger[e] ) continue ;
vector<int> fila = {e} ;
marc[e] = true ;
int ini = 0 ;
while( ini < sz(fila) )
{
int x = fila[ini++] ;
for(auto e : revAdj[x] )
{
if( marc[e] || is_charger[e] ) continue ;
if( (--deg[e]) ) continue ;
fila.pb( e ) ;
marc[e] = true ;
}
}
}
vector<int> aux ;
for(int i = 0 ; i < N ; i++ )
if( !marc[i] ) aux.pb(i) ;
if(aux.empty())
{
for(auto e : components.back()) good_for_a[e] = true ;
goUpwards(components.back()) ;
return true ;
}
//for(auto e : aux ) cout << e <<" " ;
//cout << endl ;
List.clear() ;
components.clear() ;
for(auto e : aux )
if(!marc[e]) dfs1(e) ;
for(int i : aux ) marc[i] = false ;
for(int i = sz(List)-1 ; i >= 0 ; i-- )
{
if( marc[ List[i] ] ) continue ;
components.pb(vector<int>()) ;
dfs2(List[i]) ;
}
for(auto e : aux ) marc[e] = false ;
for(int i = 0 ; i < sz(components) ; i++ )
{
bool cool = false ;
for(auto e : components[i] ) marc[e] = true ;
for(auto e : components[i] )
for( auto ee : adj[e] )
cool |= !marc[ee] ;
for(auto e : components[i] ) marc[e] = true ;
if(cool) continue ;
if( sz(components[i]) == 1 )
{
for(auto e : adj[components[i][0]]) cool |= (e == components[i][0] ) ;
cool = !cool ;
}
if(cool) continue ;
//I'm a leaf and a cycle
for(auto e : components[i]) good_for_b[e] = true ;
goUpwards(components[i]) ;
return true ;
}
return true ;
}
vector<int> who_wins( vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
N = sz(a) ;
M = sz(u) ;
good_for_a.resize( N , 0 ) ;
good_for_b.resize( N , 0 ) ;
lp(i,0,N) is_a[i] = a[i] ;
lp(i,0,N) is_charger[i] = r[i] ;
lp(i,0,M)
{
adj[ u[i] ].pb( v[i] ) ;
revAdj[ v[i] ].pb(u[i]) ;
}
while(solve()) {}
return good_for_a ;
}
