#include "train.h"
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,sse,sse2,avx2,ssse3,tune=native")
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5050;
int n, m, loop[maxn];
vector<int> g[maxn], a, r, res;
namespace s1 {
bool dfs(int v) {
if(a[v] && loop[v] && r[v]) return true;
if(!a[v] && loop[v] && !r[v]) return false;
if(g[v].size()) return dfs(v+1);
return !a[v];
}
};
void solve1() {
using namespace s1;
for(int i = 0; i < n; i++) res.push_back(dfs(i));
}
namespace brt {
};
void solvebrt() {
using namespace brt;
}
namespace s3 {
int s[maxn], dp[maxn][maxn];
void dfs(int v, int p) {
if(dp[p][v]) return;
dp[p][v] = 1;
for(int i : g[v])
dfs(i, p);
}
};
void solvef(int f) {
using namespace s3;
memset(dp, 0, sizeof dp);
for(int i = 0; i < n; i++) dfs(i, i);
for(int i = 0; i < n; i++) {
dp[i][i] = loop[i];
for(int j = 0; j < n; j++) {
s[i] |= dp[i][j]&&dp[j][i] && (r[j]||r[j]);
}
}
for(int i = 0; i < n; i++) {
int v = s[i];
for(int j = 0; j < n; j++) {
v |= dp[i][j] && s[j];
}
res.push_back(v);
}
}
std::vector<int> who_wins(std::vector<int> _a, std::vector<int> _r, std::vector<int> u, std::vector<int> v) {
n = _a.size();
m = u.size();
a = _a, r = _r;
int ss1 = 1;
set<array<int, 2>> pr;
for(int i = 0; i < m; i++) {
if(!pr.insert({u[i], v[i]}).second) continue;
if(u[i] != v[i])
g[u[i]].push_back(v[i]);
else loop[u[i]] = 1;
ss1 &= u[i] == v[i] || v[i] == u[i]+1;
}
if(ss1) solve1();
//else if(n < 16) solvebrt();
else solvef(count(a.begin(), a.end(), 1) == n);
return res;
}
