#include "train.h"
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define sz(x) (int((x).size()))
vi solve(vi a, vi r, vi u, vi v) {
int n = sz(a), m = sz(u);
vvi G(n, vi()); for (int i = 0; i < m; i++) G[u[i]].push_back(v[i]);
vi res(n, 0);
set<int> far; for (int i = 0; i < n; i++) if (r[i]) far.insert(i);
for (int x = 0; x < n; x++) {
for (int i = 0; i < n; i++) {
int cnt = 0;
for (auto v : G[i]) if (far.count(v)) cnt++;
if (a[i] == 1 && cnt>0) far.insert(i);
else if (a[i] == 0 && cnt == G[i].size()) far.insert(i);
}
}
if (far.size() == n) {
return vi(n, 1);
}
set<int> removed; for (int i = 0; i < n; i++) if (!far.count(i)) removed.insert(i);
vi a2, r2, u2, v2, id(n, -1), rmap(n, -1);
int cmp = 0;
for (int i = 0; i < n; i++) {
if (removed.count(i)) continue;
a2.push_back(a[i]); r2.push_back(a[i]);
id[i] = cmp++; rmap[cmp-1] = i;
}
for (int i = 0; i < m; i++) {
if (removed.count(u[i]) || removed.count(v[i])) continue;
u2.push_back(id[u[i]]), v2.push_back(id[v[i]]);
}
vi res2 = solve(a2, r2, u2, v2);
for (int i = 0; i < res2.size(); i++) {
res[rmap[i]] = res2[i];
}
return res;
}
vi who_wins(vi a, vi r, vi u, vi v) {
return solve(a, r, u, v);
// int n = sz(a), m = sz(u);
// vi res(n, 0);
// return res;
}
