#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3005;
const int MAX_M = 6005;
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();
vector<int> adj[MAX_M];
for (int i = 0; i < M; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
vector<int> result;
int Q = S.size();
for (int i = 0; i < Q; i++) {
bool reachable = false;
queue<int> qs, qe;
bool visited_s[MAX_N] = {false}, visited_e[MAX_N] = {false};
if (S[i] < L[i] || E[i] > R[i]) {
result.push_back(false);
continue;
}
qs.push(S[i]); visited_s[S[i]] = true;
qe.push(E[i]); visited_e[E[i]] = true;
while (!qs.empty()) {
int n = qs.front(); qs.pop();
for (auto u: adj[n]) {
if (visited_s[u] || u < L[i]) continue;
visited_s[u] = true;
qs.push(u);
}
}
/*for (int j = 0; j < N; j++) {
cout << visited_s[j];
}
cout << endl;*/
while (!qe.empty()) {
int n = qe.front(); qe.pop();
for (auto u: adj[n]) {
if (visited_e[u] || u > R[i]) continue;
visited_e[u] = true;
if (visited_s[u]) {
reachable = true;
// break;
}
qe.push(u);
}
}
/*for (int j = 0; j < N; j++) {
cout << visited_e[j];
}
cout << endl;
cout << reachable << endl;*/
result.push_back(reachable);
}
return result;
}
