#include "werewolf.h"
//#include "grader.cpp"
#include "bits/stdc++.h"
using namespace std;
#define MAX_N 3003
int n ,m ,q;
vector <int> adj[MAX_N];
bool human(int x ,int l ,int r){
return l <= x;
}
bool wolf(int x ,int l ,int r){
return x <= r;
}
bool both(int x ,int l ,int r){
return l <= x && x <= r;
}
bool vis[2][MAX_N];
bool bfs(int s ,int e ,int l ,int r){
queue <pair<int ,bool>> nxt; nxt.push({s ,0});
memset(vis ,0 ,sizeof vis);
while(!nxt.empty()){
auto now = nxt.front(); nxt.pop();
if(vis[now.second][now.first])
continue;
vis[now.second][now.first] = 1;
if(!both(now.first ,l ,r) && !now.second && wolf(now.first ,l ,r))
continue;
if(!both(now.first ,l ,r) && now.second && human(now.first ,l ,r))
continue;
//cout << now.first << ' ' << now.second << endl;
if(now.first == e && (now.second || both(now.first , l ,r)))
return 1;
for(int v : adj[now.first]){
if(!now.second && both(now.first ,l ,r))
nxt.push({v ,0}) ,nxt.push({v ,1});
else if(!now.second)
nxt.push({v ,0});
else
nxt.push({v ,1});
}
}
return 0;
}
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R)
{
n = N ,m = X.size() ,q = S.size();
for(int i=0; i<m; i++)
adj[X[i]].push_back(Y[i]),
adj[Y[i]].push_back(X[i]);
vector <int> A(q);
for(int i=0; i<q; i++)
A[i] = bfs(S[i] ,E[i] ,L[i] ,R[i]);
return A;
}
