#include "train.h"
#include <vector>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define X first
#define Y second
#define PB push_back
#define deb(...) //fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 5e3 + 10;
int self[N], bio[N], cmp[N], ans[N];
vector<int> g[N], h[N], topo;
vector<int> c[N], cg[N];
void rec(int u) {
bio[u] = 1;
for(int v : g[u]) {
if(!bio[v]) { rec(v); }
}
topo.PB(u);
}
void cer(int u) {
bio[u] = 2;
c[cmp[u]].PB(u);
for(int v : h[u]) {
if(bio[v] == 1) { cmp[v] = cmp[u]; cer(v); }
}
deb("%d ", u);
}
void dfs(int u) {
bio[u] = 1;
for(int v : c[u]) { ans[v] = 1; }
for(int v : cg[u]) {
if(!bio[v]) { dfs(v); }
}
}
vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V) {
for(int i = 0; i < (int) U.size(); ++i) {
g[U[i]].PB(V[i]);
h[V[i]].PB(U[i]);
if(U[i] == V[i]) self[U[i]] = 1;
}
memset(bio, 0, sizeof(bio));
for(int i = 0; i < (int) A.size(); ++i) {
if(!bio[i]) { rec(i); }
}
reverse(topo.begin(), topo.end());
int cnt = 1;
for(int u : topo) {
if(bio[u] == 1) {
cmp[u] = cnt++;
cer(u);
deb("\n");
}
}
for(int i = 0; i < (int) U.size(); ++i) {
if(cmp[U[i]] != cmp[V[i]]) { cg[cmp[V[i]]].PB(cmp[U[i]]); }
}
memset(bio, 0, sizeof(bio));
for(int i = 1; i < cnt; ++i) {
int r = -1;
for(int u : c[i]) {
if(R[u]) r = u;
}
deb("%d %d %d\n", r, (int) c[i].size(), self[r]);
if(r != -1 && ((int) c[i].size() >= 2 || self[r])) {
dfs(i);
}
}
vector<int> res;
for(int i = 0; i < (int) A.size(); ++i) res.PB(ans[i]);
return res;
}
