#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
typedef long long ll;
ll n, m, q;
vector<vector<ll>> adj;
bool solve(ll s, ll e, ll l, ll r) {
queue<ll> q;
q.push(s);
vector<bool> vstH(n), vstW(n);
while (!q.empty()) {
ll node = q.front(); q.pop();
if (vstH[node]) continue;
vstH[node] = true;
for (auto &e : adj[node]) {
if (e < l) continue;
q.push(e);
}
}
q.push(e);
while (!q.empty()) {
ll node = q.front(); q.pop();
if (vstH[node]) return true;
if (vstW[node]) continue;
vstW[node] = true;
for (auto &e : adj[node]) {
if (e > r) continue;
q.push(e);
}
}
return false;
}
vector<int> check_validity(int n1, vector<int> x, vector<int> y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
n = n1; m = x.size(); q = S.size();
adj = vector<vector<ll>>(n);
for (int i = 0; i < m; i++) {
adj[x[i]].push_back(y[i]);
adj[y[i]].push_back(x[i]);
}
vector<int> res(q);
while (q--) {
ll s = S[q], e = E[q];
ll l = L[q], r = R[q];
res[q] = solve(s, e, l, r);
}
return res;
}
