#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5000;
set<int> adj[N];
vector<int> adjIn[N];
vector<int> a;
vector<int> r;
vector<int> u;
vector<int> v;
bool miss[N];
int in[N];
int up[N];
int out[N];
int timer = 0;
bool goodA[N];
bool goodB[N];
vector<int> comps;
vector<int> st;
bool onSt[N];
void dfs(int node)
{
timer++;
in[node] = timer;
up[node] = in[node];
st.push_back(node);
onSt[node] = true;
for (int next : adj[node])
{
if (miss[next]) continue;
if (next == node && r[node])
{
goodA[node] = true;
}
if (next == node) goodB[node] = true;
if (in[next] == 0)
{
dfs(next);
up[node] = min(up[node], up[next]);
} else if (onSt[next])
{
up[node] = min(up[node], in[next]);
}
}
if (in[node] == up[node])
{
vector<int> comp;
while (st.back() != node)
{
onSt[st.back()] = false;
if (r[st.back()]) goodA[st.back()] = true;
goodB[st.back()] = true;
comp.push_back(st.back());
st.pop_back();
}
comp.push_back(node);
st.pop_back();
onSt[node] = false;
if (comp.size() > 1 && r[node])
{
goodA[node] = true;
}
if (comp.size() > 1) goodB[node] = true;
}
}
bool reachable[N];
void goReach(int node)
{
reachable[node] = true;
for (int next : adjIn[node])
{
if (reachable[next]) continue;
goReach(next);
}
}
std::vector<int> who_wins(std::vector<int> A, std::vector<int> R, std::vector<int> U, std::vector<int> V) {
a = A;
r = R;
u = U;
v = V;
int n = a.size();
int m = u.size();
bool simple = true;
for (int i = 0; i < m; i++)
{
if (!(v[i] == u[i] || v[i] == u[i] + 1)) simple = false;
adj[u[i]].insert(v[i]);
adjIn[v[i]].push_back(u[i]);
}
std::vector<int> res(a.size());
bool allA = true;
bool allB = true;
for (int i = 0; i < n; i++)
{
if (a[i] == 1) allB = false;
if (a[i] == 0) allA = false;
}
//cout << simple << endl;
if (simple)
{
for (int i = 0; i < n; i++)
{
int cur = i;
bool good = false;
int travelled = 0;
while (travelled < n)
{
if (a[cur] == 1)
{
if (r[cur] == 1)
{
if (adj[cur].find(cur) != adj[cur].end())
{
good = true;
break;
}
}
for (int next : adj[cur])
{
if (next != cur)
{
cur = next;
break;
}
}
} else
{
if (r[cur] != 1)
{
if (adj[cur].find(cur) != adj[cur].end())
{
break;
}
}
for (int next : adj[cur])
{
if (next != cur)
{
cur = next;
break;
}
}
}
travelled++;
}
if (r[cur]) good = true;
res[i] = good;
}
return res;
} else if (allA)
{
for (int i = 0; i < n; i++)
{
if (!in[i]) dfs(i);
}
for (int i = 0; i < n; i++)
{
if (goodA[i] && !reachable[i]) goReach(i);
}
for (int i = 0; i < n; i++) res[i] = reachable[i];
return res;
} else if (allB)
{
for (int i = 0; i < n; i++) if (r[i]) miss[i] = true;
for (int i = 0; i < n; i++)
{
if (!miss[i] && !in[i]) dfs(i);
}
for (int i = 0; i < n; i++)
{
if (goodB[i] && !reachable[i]) goReach(i);
}
for (int i = 0; i < n; i++)
{
res[i] = !reachable[i];
}
return res;
}
return res;
}
/*
10 11
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0
0 1
1 2
2 1
1 3
1 4
4 5
5 4
6 6
7 7
8 9
9 8
*/
