#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
struct Graph{
int n,m;
vi a,r,ord,vis,C,CS,CR,S,CO;
vvi G,Gco,CC,CG;
void dfs1(int v){
if(vis[v]) return;
vis[v] = 1;
for(int u : G[v]) dfs1(u);
ord.push_back(v);
}
void dfs2(int v){
if(vis[v]) return;
vis[v] = 1;
CC.back().push_back(v);
for(int u : Gco[v]) dfs2(u);
}
void CCC(){
vis.assign(n+1,0);
dfs1(n);
vis.assign(n+1,0);
CC = {{}};
for(int i = n-1;i>=0;i--){
dfs2(ord[i]);
if(CC.back().size()) CC.push_back({});
}
CC.pop_back();
C.assign(n,0);
for(int i = 0;i < CC.size();i++) for(int v : CC[i]) C[v] = i;
CG.assign(CC.size(),{});
for(int u = 0;u < n;u++) for(int v : G[u]) CG[C[u]].push_back(C[v]);
for(int c = 0;c < CC.size();c++){
sort(CG[c].begin(),CG[c].end());
CG[c].erase(unique(CG[c].begin(),CG[c].end()),CG[c].end());
}
CR.assign(CC.size(),0);
for(int i = 0;i < n;i++) CR[C[i]] = max(CR[C[i]],r[i]);
vi CD(CC.size(),0);
for(int c = 0;c < CC.size();c++) for(int d : CG[c]) if(d != c) CD[d]++;
vi curr;
for(int i = 0;i < CC.size();i++) if(!CD[i]) curr.push_back(i);
for(;curr.size();){
int c = curr.back();
CO.push_back(c);
curr.pop_back();
for(int d : CG[c]) if(!--CD[d]) curr.push_back(d);
}
}
Graph(vi a, vi r2, vi u, vi v) : a(a), r(r2) {
n = a.size(), m = u.size();
G.assign(n+1,{}), Gco = G;
for(int i = 0;i < m;i++) G[u[i]].push_back(v[i]), Gco[v[i]].push_back(u[i]);
for(int i = 0;i < n;i++) G[n].push_back(i);
for(int i = 0;i < n;i++) if(r[i] && find(G[i].begin(),G[i].end(),i) != G[i].end()) r[i] = 2;
CCC();
CS.assign(CC.size(),0);
for(int o = CC.size()-1,c;o >= 0;o--){
c = CO[o];
if(CR[c] && max(CR[c],(int)CC[c].size()) > 1) CS[c] = 1;
for(int d : CG[c]) if(CS[d]) CS[c] = 1;
}
S.assign(n,0);
for(int i = 0;i < n;i++) S[i] = CS[C[i]];
}
};
vi who_wins(vi a, vi r, vi u, vi v) {
Graph G(a,r,u,v);
return G.S;
}
