#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
int q, n, m;
vector<int> gr[400005];
bool dost[400005][2];
void dfs(int v, int ty, int Le, int Ri)
{
dost[v][ty]=1;
if(ty==0 && v<=Ri && !dost[v][1]) dfs(v, 1, Le, Ri);
int brs=gr[v].size();
for(int i=0; i<brs; i++)
{
int nv=gr[v][i];
if(dost[nv][ty]) continue;
if(nv<=Ri && ty==1) dfs(nv, ty, Le, Ri);
if(nv>=Le && ty==0) dfs(nv, ty, Le, Ri);
}
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R)
{
q=S.size();
n=N;
m=X.size();
for(int i=0; i<m; i++)
{
gr[X[i]].push_back(Y[i]);
gr[Y[i]].push_back(X[i]);
}
vector<int> A;
A.resize(q);
for(int i=0; i<q; i++)
{
memset(dost, 0, sizeof(dost));
dfs(S[i], 0, L[i], R[i]);
A[i]=dost[E[i]][1];
}
return A;
}
