#include "werewolf.h"
#include <queue>
#include <vector>
using namespace std;
queue < pair < int , int > > all;
vector < int > Next[200005];
bool have[5][200005];
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(),i,j,ok,a,b;
vector<int> A(Q);
for(i=0;i<M;i++)
{
Next[X[i]].push_back(Y[i]);
Next[Y[i]].push_back(X[i]);
}
for (i=0;i<Q;i++)
{
for(j=0;j<N;j++) have[0][j]=have[1][j]=0;
ok=0;
all.push(make_pair(S[i],0));
while(!all.empty())
{
a=all.front().first;
b=all.front().second;
all.pop();
if(a==E[i]&&b==1)
{
ok=1;
break;
}
if(have[b][a]) continue;
if(b==0&&a<L[i]) continue;
if(b==1&&a>R[i]) continue;
have[b][a]=1;
if(b==0&&a>=L[i]&&a<=R[i]) all.push(make_pair(a,1));
for(auto i:Next[a]) all.push(make_pair(i,b));
}
while(!all.empty()) all.pop();
A[i]=ok;
}
return A;
}
