#include "werewolf.h"
#include <bits/stdc++.h>
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;
typedef vector<int> vi;
const int MAXN = (int)2e5 + 5;
const int MAXM = (int)4e5 + 5;
const int MAXQ = (int)2e5 + 5;
vector <int> g[MAXN];
int N, M, Q;
struct Query {
int s, e, l, r;
Query (int s_, int e_, int l_, int r_) {
s = s_, e = e_, l = l_, r = r_;
}
Query () {
}
}query[MAXQ];
struct Small_Solve {
bool need = false;
vector <int> ans;
void solve() {
ans.resize(Q, 0);
vector <int> used[3];
used[1].resize(N, 0);
used[2].resize(N, 0);
int cnt = 0;
for (int i = 0; i < Q; i++) {
cnt++;
queue <int> q[3];
if (query[i].s >= query[i].l) {
q[1].push(query[i].s);
}
if (query[i].e <= query[i].r) {
q[2].push(query[i].e);
}
while (!q[1].empty()) {
int v = q[1].front();
q[1].pop();
if (used[1][v] == cnt) {
continue;
}
used[1][v] = cnt;
for (int to : g[v]) {
if (to >= query[i].l) {
q[1].push(to);
}
}
}
while (!q[2].empty()) {
int v = q[2].front();
q[2].pop();
if (used[2][v] == cnt) {
continue;
}
used[2][v] = cnt;
for (int to : g[v]) {
if (to <= query[i].r) {
q[2].push(to);
}
}
}
int found = 0;
for (int v = 0; v < N; v++) {
found |= (used[1][v] == cnt && used[2][v] == cnt);
}
ans[i] = found;
}
}
}subtask12;
bool bambook() {
return false;
}
std::vector<int> check_validity(int NN, vi X, vi Y, vi S, vi E, vi L, vi R) {
N = NN;
M = szof(X);
Q = szof(S);
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++) {
query[i] = Query(S[i], E[i], L[i], R[i]);
}
if (N <= 3000 && M <= 6000 && Q <= 3000) {
subtask12.need = true;
subtask12.solve();
return subtask12.ans;
}
else if (bambook() == true) {
}
assert(false);
}
