#include <bits/stdc++.h>
#include "train.h"
using namespace std;
typedef long long ll;
vector<unordered_set<ll>> adj, revAdj;
vector<bool> vst;
bool poss = false;
vector<int> a;
void dfs1(ll cur, ll root) {
vst[cur] = true;
for (auto &e : revAdj[cur]) {
if (e == root) poss = true;
if (vst[e]) continue;
dfs1(e, root);
}
}
void dfs2(ll cur, ll par, bool can) {
vst[cur] = true;
if (cur == par) {
for (auto &e : revAdj[cur]) {
if (vst[e]) continue;
dfs2(e, cur, true);
}
return;
}
if (a[cur] != can) {
if (adj[cur].size() > 1) {
adj[cur].erase(par);
for (auto &e : revAdj[cur]) {
if (vst[e]) continue;
dfs2(e, cur, !can);
}
}
else {
for (auto &e : revAdj[cur]) {
if (vst[e]) continue;
dfs2(e, cur, can);
}
}
}
else {
adj[cur].clear();
adj[cur].insert(par);
for (auto &e : revAdj[cur]) {
if (vst[e]) continue;
dfs2(e, cur, can);
}
}
}
vector<int> who_wins(vector<int> a1, vector<int> r, vector<int> u, vector<int> v) {
a = a1;
ll n = a.size(), m = u.size();
vector<int> res(n);
adj = vector<unordered_set<ll>>(n);
revAdj = vector<unordered_set<ll>>(n);
for (int i = 0; i < m; i++) {
adj[u[i]].insert(v[i]);
revAdj[v[i]].insert(u[i]);
}
ll charge = 0;
for (int i = 0; i < n; i++) {
if (r[i]) {
charge = i;
break;
}
}
vst = vector<bool>(n);
dfs2(charge, charge, true);
revAdj = vector<unordered_set<ll>>(n);
for (int i = 0; i < n; i++) {
for (auto &e : adj[i]) {
revAdj[e].insert(i);
}
}
vst = vector<bool>(n);
poss = false;
dfs1(charge, charge);
vector<bool> vst2 = vst;
vst = vector<bool>(n);
adj = vector<unordered_set<ll>>(n);
revAdj = vector<unordered_set<ll>>(n);
for (int i = 0; i < m; i++) {
adj[u[i]].insert(v[i]);
revAdj[v[i]].insert(u[i]);
}
poss = false;
dfs1(charge, charge);
if (poss) {
for (int j = 0; j < n; j++) {
if (!vst2[j]) continue;
res[j] = true;
}
}
return res;
}
