#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
int Q = L.size();
int M = X.size();
vi ans(Q);
vvi adj(N);
for (int i = 0; i < M; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for (int t = 0; t < Q; t++) {
int l = L[t], r = R[t];
int s = S[t], e = E[t];
vvi seen(2, vi(N));
queue<pii> q;
q.push({s, 0});
while (q.size()) {
auto [u, wolf] = q.front(); q.pop();
if (seen[wolf][u]) continue;
seen[wolf][u] = 1;
if (u >= l && u <= r && !wolf) q.push({u, 1});
for (int v : adj[u]) {
if (v >= l && !wolf && !seen[0][v]) q.push({v, 0});
if (v <= r && wolf && !seen[1][v]) q.push({v, 1});
}
if (seen[1][e]) break;
}
ans[t] = seen[1][e];
}
return ans;
}
