#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;
#define forR(i, n) for (int i = 0; i < (n); i++)
int n, m, q;
Vii nbs;
int calc(int s, int e, int l, int r) { // [l, inf) --> [0, r]
if (s < l || e > r || l > r) return 0;
Vb inS(n), inE(n);
// pathfind 1: from s, >= l
queue<int> q; q.push(s); inS[s] = true;
while (!q.empty()) {
int x = q.front(); q.pop();
for (int nb : nbs[x]) {
if (inS[nb] == false && nb >= l) {
inS[nb] = true;
q.push(nb);
}
}
}
// pathfind 2: from e, <= r
q = queue<int>(); q.push(e); inE[e] = true;
if (inS[e]) return 1;
while (!q.empty()) {
int x = q.front(); q.pop();
for (int nb : nbs[x]) {
if (inE[nb] == false && nb <= r) {
inE[nb] = true;
q.push(nb);
if (inS[nb]) {
// transform at nb, succeed
return 1;
}
}
}
}
return 0;
}
Vi check_validity(int N, Vi X, Vi Y, Vi S, Vi E, Vi L, Vi R) {
n = N; m = X.size(); q = S.size();
nbs = Vii(n);
forR(i, m) {
nbs[X[i]].push_back(Y[i]);
nbs[Y[i]].push_back(X[i]);
}
Vi result;
forR(i, q) {
result.push_back(calc(S[i], E[i], L[i], R[i]));
}
return result;
}
#ifdef TEST_LOCAL_
int main() {
auto result = check_validity(6, Vi{ 5, 1, 1, 3, 3, 5 }, Vi{ 1, 2, 3, 4, 0, 2 }, Vi{ 4, 4, 5 }, Vi{ 2, 2, 4 }, Vi{ 1, 2, 3 }, Vi{ 2, 2, 4 });
return 0;
}
#endif
