#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;
bool T3 = false;
Vi qt3, t3PosOf;
struct Range {
int l, r;
bool contains(int t) {
return l <= t && t <= r;
}
static bool overlaps(Range r1, Range r2) {
return r1.contains(r2.l) || r2.contains(r1.l);
}
};
struct SegNode {
int l, r;
SegNode* left, * right;
int minV, maxV;
Range RangeGe(int t, int L) { // >= L
if (t < l || t > r) return Range{ -1, -2 };
if (minV >= L) return Range{ l, r };
if (l == r) return Range{ -1, -2 };
if (left->contains(t)) {
auto range = left->RangeGe(t, L);
if (range.r == left->r) {
auto rR = right->RangeGe(right->l, L);
if (rR.l == right->l) range.r = rR.r;
}
return range;
} else {
assert(right->contains(t));
auto range = right->RangeGe(t, L);
if (range.l == right->l) {
auto rL = left->RangeGe(left->r, L);
if (rL.r == left->r) range.l = rL.l;
}
return range;
}
}
Range RangeLe(int t, int R) { // <= R
if (t < l || t > r) return Range{ -1, -2 };
if (maxV <= R) return Range{ l, r };
if (l == r) return Range{ -1, -2 };
if (left->contains(t)) {
auto range = left->RangeLe(t, R);
if (range.r == left->r) {
auto rR = right->RangeLe(right->l, R);
if (rR.l == right->l) range.r = rR.r;
}
return range;
} else {
assert(right->contains(t));
auto range = right->RangeLe(t, R);
if (range.l == right->l) {
auto rL = left->RangeLe(left->r, R);
if (rL.r == left->r) range.l = rL.l;
}
return range;
}
}
inline bool contains(int t) {
return l <= t && t <= r;
}
SegNode(int l, int r) {
this->l = l; this->r = r;
if (l == r) {
left = right = nullptr;
minV = maxV = qt3[l];
} else {
int mid = (l + r) / 2;
left = new SegNode(l, mid);
right = new SegNode(mid + 1, r);
minV = min(left->minV, right->minV);
maxV = max(left->maxV, right->maxV);
}
}
}*root;
void initT3() {
int head;
forR(i, n) if (nbs[i].size() == 1) {
head = i;
break;
}
Vb inT3(n); t3PosOf = Vi(n);
inT3[head] = true; qt3.push_back(head);
int next = -1;
for (int x = head; x >= 0; x = next) {
next = -1;
for (int nb : nbs[x]) {
if (!inT3[nb]) {
inT3[nb] = true;
t3PosOf[nb] = qt3.size();
qt3.push_back(nb);
next = nb;
}
}
}
root = new SegNode(0, n - 1);
}
int calcT3(int s, int e, int l, int r) { // [l, inf) --> [0, r]
int ps = t3PosOf[s], pe = t3PosOf[e];
auto rangeS = root->RangeGe(ps, l);
auto rangeE = root->RangeLe(pe, r);
if (Range::overlaps(rangeS,rangeE)) {
return 1;
}
return 0;
}
int calc(int s, int e, int l, int r) { // [l, inf) --> [0, r]
if (s < l || e > r || l > r) return 0;
if (T3) return calcT3(s, e, l, r);
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]);
}
int nbs_cnt_max = 0;
forR(i, n) nbs_cnt_max = max(nbs_cnt_max, (int)nbs[i].size());
if (nbs_cnt_max == 2 && m == n - 1) {
T3 = true;
initT3();
}
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
