#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
int n, m;
int be, en, le, ri;
vector<int> res;
vector<int> gr[3005];
bool used[3005][2];
void dfs(int v, int ty)
{
used[v][ty]=1;
if(ty==0 && v<=ri && !used[v][1]) dfs(v, 1);
int brs=gr[v].size();
for(int i=0; i<brs; i++)
{
int nv=gr[v][i];
if(ty==0 && nv<le) continue;
if(ty==1 && nv>ri) continue;
if(used[nv][ty]) continue;
dfs(nv, ty);
}
}
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)
{
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]);
}
int q=S.size();
for(int i=0; i<q; i++)
{
be=S[i], en=E[i], le=L[i], ri=R[i];
if(be<le || en>ri) {res.push_back(0); continue;}
memset(used, 0, sizeof(used));
dfs(be, 0);
res.push_back(used[en][1]);
}
return res;
}
