#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
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();
int M = X.size();
vector< vector< int > > Graph(N);
for(int i = 0; i < M; i++){
Graph[X[i]].push_back(Y[i]);
Graph[Y[i]].push_back(X[i]);
}
vector<int> A(Q);
for(int j = 0; j < Q; j++){
vector< bool > Human(N, false);
if(S[j] < L[j] || E[j] > R[j]){
A[j] = 0;
continue;
}
queue< int > q;
q.push(S[j]);
Human[S[j]] = true;
while(!q.empty()){
int node = q.front();
q.pop();
for(int neighbours : Graph[node]){
if(Human[neighbours]) continue;
if(neighbours < L[j]) continue;
Human[neighbours] = true;
q.push(neighbours);
}
}
q.push(E[j]);
vector< bool > visited(N, false);
visited[E[j]] = true;
while(!q.empty()){
int node = q.front();
q.pop();
for(int neigh : Graph[node]){
if(neigh > R[j] || visited[neigh]){
continue;
}
visited[neigh] = true;
q.push(neigh);
}
}
bool verif = false;
for(int i = 0; i < N; i++){
if(Human[i] && visited[i]){
A[j] = 1;
verif = true;
break;
}
}
if(!verif) A[j] = 0;
}
return A;
}
