#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], r[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] && !r[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 && !r[v]) { cmp[v] = cmp[u]; cer(v); }
}
deb("%d ", u);
}
void dfs(int u, int &val) {
if(ans[u]) {
val = 1;
return;
}
bio[u] = 1;
for(int v : g[u]) {
if(!bio[v]) { dfs(v, val); }
}
return;
}
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;
}
for(int i = 0; i < (int) A.size(); ++i) r[i] = R[i];
memset(bio, 0, sizeof(bio));
for(int i = 0; i < (int) A.size(); ++i) {
if(!r[i] && !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 = 1; i < cnt; ++i) {
if((int) c[i].size() >= 2 || self[c[i][0]]) {
for(int u : c[i]) { ans[u] = 1; }
}
}
vector<int> res((int) A.size());
for(int i = 0; i < (int) A.size(); ++i) { memset(bio, 0, sizeof(bio)); dfs(i, res[i]); }
return res;
}
