#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
///Subtask 2
///DFS in a 3D graph
vector<int> adjList[6005];
int destiny;
int color[6005];
int c=0;
int n;
int l,r;
int dfsVisit(int u)
{
if(u==destiny) return 1;
int ans=0;
color[u]=c;
for(int v: adjList[u]){
if(ans==1) break;
if(color[v]!=c){
if(v!=u+n){
if(v<n && v>=l)
ans=dfsVisit(v);
if(v>=n && v<=r+n)
ans=dfsVisit(v);
}
if(v==u+n && l<=u && u<=r)
ans=dfsVisit(v);
}
}
return ans;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> T, vector<int> L, vector<int> R) {
int m=X.size();
int Q=S.size();
n=N;
for(int i=0;i<m;i++){
int a=X[i];
int b=Y[i];
adjList[a].push_back(b);
adjList[b].push_back(a);
adjList[a+n].push_back(b+n);
adjList[b+n].push_back(a+n);
}
for(int i=0;i<n;i++){
adjList[i].push_back(i+n);
}
vector<int> A;
for(int i=0;i<Q;i++){
c++;
destiny=T[i]+n;
l=L[i];
r=R[i];
A.push_back(dfsVisit(S[i]));
}
return A;
}
