#include "train.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define pb emplace_back
#define mp make_pair
#define MAXN 5010
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
vi V[MAXN], U[MAXN];
int lowlink[MAXN], vis[MAXN], ind[MAXN],SCC[MAXN];
int a=1,b=1,N;
int curstack[MAXN];
int A[MAXN];
stack<int> stk;
vi res;
int hg[MAXN];
int selfedge[MAXN];
void dfs(int x){
if (ind[x]!=-1)return;
ind[x] = lowlink[x] = a++;
curstack[x]=1;
stk.push(x);
for (auto v : V[x]){
if(SCC[v]!=-1)continue;
if(ind[v] == -1){
dfs(v);
lowlink[x] = min(lowlink[v], lowlink[x]);
continue;
}else if (curstack[v]){
lowlink[x] = min(lowlink[x],ind[v]);
}
}
// cout<<x<<' '<<ind[x]<<' '<<lowlink[x]<<'\n';
if (lowlink[x] == ind[x]){
while(stk.top()!=x){
curstack[stk.top()]=0;
SCC[stk.top()] = b;
stk.pop();
}
stk.pop();
SCC[x]=b++;
}
}
void dfs2(int x){
res[x] =1;
for (auto i : U[x])if(vis[i]==0){
vis[i] = 1;
dfs2(i);
}
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
N = SZ(a);
res.resize(N,0);
memset(ind,-1,sizeof(ind));
memset(SCC,-1,sizeof(SCC));
for (int i=0;i<N;++i)assert(a[i]==0);
int m = SZ(u);
for (int i=0;i<m;++i){
U[v[i]].pb(u[i]);
if (u[i]==v[i])selfedge[u[i]]=1;
if (r[u[i]] || r[v[i]])continue;
V[u[i]].pb(v[i]);
// cout<<u[i]<<' '<<v[i]<<'\n';
}
vi mem(N,0);
for (int i=0;i<N;++i){
if (r[i])continue;
if (vis[i])continue;
dfs(i);
}
for (int i=0;i<N;++i)if (!r[i])hg[SCC[i]]++;
// for (int i=0;i<N;++i)cout<<SCC[i]<<' ';cout<<'\n';
for (int i=0;i<N;++i)if(!r[i]){
if (hg[SCC[i]] == 1){
if (!selfedge[i])continue;
}
mem[SCC[i]] = 1;
}
for (int i=0;i<N;++i)if(mem[SCC[i]]){
memset(vis,0,sizeof(vis));
// cout<<"DFS 2 "<<i <<'\n';
vis[i]=1;
dfs2(i);
}
return res;
}
