#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 3e3 + 10;
vector<int> g[mxn];
bool pos(int start, int end, int l, int r) {
bool visitedH[mxn], visitedW[mxn];
memset(visitedH, 0, sizeof(visitedH));
memset(visitedW, 0, sizeof(visitedW));
queue<int> q;
q.push(start);
visitedH[start] = 1;
while (q.size()) {
int pos = q.front();
q.pop();
for (auto x : g[pos]) {
if (!visitedH[x] && x >= l) {
visitedH[x] = 1;
q.push(x);
}
}
}
q.push(end);
visitedW[end] = 1;
while (q.size()) {
int pos = q.front();
q.pop();
if (visitedH[pos]) return 1;
for (auto x : g[pos]) {
if (!visitedW[x] && x <= r) {
visitedW[x] = 1;
q.push(x);
}
}
}
return 0;
}
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 = X.size();
int Q = S.size();
vector<int> A(Q);
for (int i = 0; i < M; i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
for (int i = 0; i < Q; i++) A[i] = pos(S[i], E[i], L[i], R[i]);
return A;
}
