#include <bits/stdc++.h>
using namespace std;
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();
int Q = S.size();
vector<vector<int>> G(N);
for (int i = 0; i < M; i++){
G[X[i]].push_back(Y[i]);
G[Y[i]].push_back(X[i]);
}
vector<int> ans(Q, 0);
for (int i = 0; i < Q; i++){
vector<bool> used1(N, false);
used1[S[i]] = true;
queue<int> q1;
q1.push(S[i]);
while (!q1.empty()){
int v = q1.front();
q1.pop();
for (int w : G[v]){
if (w >= L[i] && !used1[w]){
used1[w] = true;
q1.push(w);
}
}
}
vector<bool> used2(N, false);
used2[E[i]] = true;
queue<int> q2;
q2.push(E[i]);
while (!q2.empty()){
int v = q2.front();
q2.pop();
for (int w : G[v]){
if (w <= R[i] && !used2[w]){
used2[w] = true;
q2.push(w);
}
}
}
for (int j = 0; j < N; j++){
if (used1[j] && used2[j]){
ans[i] = 1;
}
}
}
return ans;
}
