#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
vector< vector<int> > Grafo, Visitados;
bool Bien(int Nodo, int Objetivo, bool Humano, int No_humano, int No_lobo){
if(Nodo == Objetivo and (!Humano or (Nodo >= No_humano and Nodo <= No_lobo))) return 1;
if((Nodo < No_humano and Humano) or (Nodo > No_lobo and !Humano)) return 0;
Visitados[Nodo][Humano] = 1;
bool r = 0;
for(auto E: Grafo[Nodo]){
if(!Visitados[E][Humano]) r = r or Bien(E, Objetivo, Humano, No_humano, No_lobo);
if(Nodo >= No_humano and Nodo <= No_lobo and Humano) r = r or Bien(E, Objetivo, 0, No_humano, No_lobo);
}
return r;
}
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r){
int q = s.size(), m = x.size();
vector<int> a(q);
Grafo.assign(n, {});
for(int i = 0; i < m; i++){
Grafo[x[i]].push_back(y[i]);
Grafo[y[i]].push_back(x[i]);
}
for(int i = 0; i < q; i++){
Visitados.assign(n, vector<int>(2, 0));
a[i] = Bien(s[i], e[i], 1, l[i], r[i]) or (Bien(s[i], e[i], 0, l[i], r[i]) and s[i] >= l[i] and s[i] <= r[i]);
}
return a;
}
