#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=4e5+5;
vector<int> respf, g[MAXN];
int aresta[MAXN][2];
int n, m, q;
bool bfs(int ori, int dest, int l, int r) {
int lobo[MAXN], homem[MAXN];
memset(lobo, 0, sizeof(lobo));
memset(homem, 0, sizeof(homem));
if(ori<l) return 0;
if(dest>r) return 0;
homem[ori]=1;
for(int i=0; i<n; i++) {
for(int i=0; i<m; i++) {
int a=aresta[i][0]; int b=aresta[i][1];
if(homem[a]) {
if(b>=l) homem[b]=1;
}
if(lobo[a]) {
if(b<=r) lobo[b]=1;
}
if(homem[b]) {
if(a>=l) homem[a]=1;
}
if(lobo[b]) {
if(a<=r) lobo[a]=1;
}
if(homem[a]&&l<=a&&a<=r) lobo[a]=1;
if(homem[b]&&l<=b&&b<=r) lobo[b]=1;
}
}
return lobo[dest];
}
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();
q=S.size();
for(int i=0; i<m; i++) {
int a=X[i]; int b=Y[i];
g[a].push_back(b);
g[b].push_back(a);
aresta[i][0]=a;
aresta[i][1]=b;
}
for(int i=0; i<q; i++) {
int a=S[i]; int b=E[i];
int c=L[i]; int d=R[i];
printf("aadahb %d %d %d %d\n", a, b, c, d);
int val=bfs(a, b, c, d);
respf.push_back(val);
}
return respf;
}
