#include "train.h"
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define vb vector<bool>
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
const int mxn = 5e3 + 5;
using namespace std;
vvi adj(mxn), revadj(mxn);
int n, m;
std::vector<signed> who_wins(std::vector<signed> a, std::vector<signed> r, std::vector<signed> u, std::vector<signed> v) {
n = a.size(); m = u.size();
vi nxt(n);
vi cyc(n);
f0r(i, m){
if(u[i] + 1 == v[i])nxt[u[i]] = 1;
else cyc[u[i]] = 1;
adj[u[i]].pb(v[i]);
revadj[v[i]].pb(u[i]);
}
bool s3 = 1;
bool s2 = 1;
f0r(i, n){
if(a[i])s3 = 0;
if(!a[i])s2 = 0;
}
vector<signed> ans(n);
if(s3){
vb good(n); //is there any loop without a charger containing me?
f0r(i, n){
if(r[i] == 0){
queue<int>q;
q.push(i);
vb vis(n); vis[i] = 1;
while(!q.empty()){
int node = q.front();
q.pop();
for(auto u : adj[node]){
if(r[u])continue;
if(vis[u])continue;
vis[u] = 1;
q.push(u);
}
}
for(auto u : revadj[i]){
if(vis[u])good[i] = 1;
}
}
}
// for(auto u : good)cout<<u<<' '; cout<<endl;
f0r(i,n)ans[i] = 1;
f0r(i, n){
queue<int>q;
q.push(i);
vb vis(n); vis[i] = 1;
while(!q.empty()){
int node = q.front();
q.pop();
for(auto u : adj[node]){
if(vis[u])continue;
vis[u] = 1;
q.push(u);
}
}
f0r(j, n){
if(vis[j] && good[j])ans[i] = 0;
}
}
}
else if(s2){
vb good(n); //is there a loop with me? (must be charger)
f0r(i, n){
if(r[i] == 1){
queue<int>q;
q.push(i);
vb vis(n); vis[i] = 1;
while(!q.empty()){
int node = q.front();
q.pop();
for(auto u : adj[node]){
if(vis[u])continue;
vis[u] = 1;
q.push(u);
}
}
for(auto u : revadj[i]){
if(vis[u])good[i] = 1;
}
}
}
// for(auto u : good)cout<<u<<' '; cout<<endl;
f0r(i,n)ans[i] = 0;
f0r(i, n){
queue<int>q;
q.push(i);
vb vis(n); vis[i] = 1;
while(!q.empty()){
int node = q.front();
q.pop();
for(auto u : adj[node]){
if(vis[u])continue;
vis[u] = 1;
q.push(u);
}
}
f0r(j, n){
if(vis[j] && good[j])ans[i] = 1;
}
}
}
else{
f0r(tt, n){
int x = tt;
if(cyc[x] && a[x] == 1 && r[x] == 1){
ans[tt] = 1; continue;
}
if(cyc[x] && a[x] == 0 && r[x] == 0){
ans[tt] = 0; continue;
}
bool ok = 0;
while(nxt[x]){
x++;
if(cyc[x] && a[x] == 1 && r[x] == 1){
ans[tt] = 1; ok = 1; break;
}
if(cyc[x] && a[x] == 0 && r[x] == 0){
ans[tt] = 0; ok = 1; break;
}
}
if(ok)continue;
if(cyc[x] && r[x])ans[tt] = 1;
else ans[tt] = 0;
}
}
return ans;
}
