#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;
vvi G,Gco,CC,CG;
void dfs1(int v){
if(vis[v]) return;
vis[v] = 1;
ord.push_back(v);
for(int u : G[v]) dfs1(u);
}
void dfs2(int v){
if(vis[v]) return;
vis[v] = 1;
CC.back().push_back(v);
for(int u : Gco[v]) dfs1(u);
}
void CCC(){
vis.assign(n+1,0);
dfs1(n);
vis.assign(n+1,0);
CC = {{}};
for(int i = 1;i <= n;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]);
}
Graph(vi a, vi r, vi u, vi v) : a(a), r(r) {
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 c = CC.size()-1;c >= 0;c--){
if(CR[c] && max(CR[c],(int)CC.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;
}
