#include "werewolf.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define pb push_back
using namespace std;
const int MAXN = 3005 ;
bool visited0[MAXN] , visited1[MAXN] ;
vector<int> adj[MAXN] ;
void dfs0(int u,int x){
if(u>x)return ;
visited0[u] = 1 ;
for(int v : adj[u]){
if( !visited0[v] ){
dfs0(v,x);
}
}
}
void dfs1(int u,int x){
if(u<x)return ;
visited1[u] = 1 ;
for(int v : adj[u]){
if( !visited1[v] ){
dfs1(v,x);
}
}
}
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 M = sz(X);
for(int i = 0 ; i < M ; i++ ){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
int Q =sz(S);
vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
A[i] = 0 ;
memset(visited1,0,sizeof visited1) ;
memset(visited0,0,sizeof visited0) ;
dfs0(E[i],R[i]);
dfs1(S[i],L[i]);
for(int j = L[i] ;j <= R[i];j++){
A[i]|= (visited0[j]&&visited1[j]);
}
}
return A;
}
/*
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
int N = read_int();
int M = read_int();
int Q = read_int();
std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
for (int j = 0; j < M; ++j) {
X[j] = read_int();
Y[j] = read_int();
}
for (int i = 0; i < Q; ++i) {
S[i] = read_int();
E[i] = read_int();
L[i] = read_int();
R[i] = read_int();
}
std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
for (size_t i = 0; i < A.size(); ++i) {
printf("%d\n", A[i]);
}
return 0;
}
*/
