#include "train.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
vector <int> g[N];
int n;
int on[N], typ[N];
int mark[N], h[N], dp[N];
vector <int> backedge[N];
vector <int> dfs_tree[N];
vector <int> aux[N];
void dfs(int v, int p){
mark[v] = 1;
for(auto x : g[v]){
if(mark[x] and h[x] <= h[v]){
backedge[v].push_back(x);
continue;
}
if(h[x] > h[v]){
aux[v].push_back(x);
continue;
}
dfs_tree[v].push_back(x);
h[x] = h[v]+1;
dp[x] = dp[v];
if(on[x]) dp[x] = x;
dfs(x, v);
}
return;
}
int solve[N];
void calc(int v, int p){
if(typ[v] == 1){
solve[v] = 0;
for(auto x : dfs_tree[v]){
calc(x, v);
if(solve[x]){
solve[v] = 1;
return;
}
}
for(auto x : aux[v]){
if(solve[x]){
solve[v] = 1;
return;
}
}
if(dp[v] == -1) return;
for(auto x : backedge[v]){
if(h[x] <= h[dp[v]]){
solve[v] = 1;
return;
}
}
return;
}
else{
solve[v] = 1;
for(auto x : dfs_tree[v]){
calc(x, v);
if(solve[x] == 0){
solve[v] = 0;
return;
}
}
for(auto x : aux[v]){
if(solve[x] == 0){
solve[v] = 0;
return;
}
}
for(auto x : backedge[v]){
if(dp[v] == -1){
solve[v] = 0;
return;
}
if(h[x] > h[dp[v]]){
solve[v] = 0;
return;
}
}
return;
}
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
for(int i = 0;i < u.size();i++){
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
n = a.size();
for(int i = 0;i < n;i++){
on[i] = r[i];
typ[i] = a[i];
}
std::vector<int> res;
for(int raiz = 0;raiz < n;raiz++){
memset(mark,0, sizeof mark);
memset(h, 0, sizeof h);
memset(dp, -1, sizeof dp);
memset(solve, -1, sizeof solve);
for(int i = 0;i < n;i++){
backedge[i].clear();
dfs_tree[i].clear();
aux[i].clear();
}
if(on[raiz]) dp[raiz] = raiz;
dfs(raiz, raiz);
calc(raiz, raiz);
/*for(int i = 0;i < n;i++){
cout << i << ": ";
for(auto x : dfs_tree[i]){
cout << x << ' ';
}
cout << endl;
for(auto x : aux[i])
cout << x << ' ';
cout << endl;
for(auto x : backedge[i])
cout << x << ' ';
cout << endl;
}*/
res.push_back(solve[raiz]);
}
return res;
}
