#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p;
DSU(int n=0){ init(n); }
void init(int n){
p.resize(n+1);
iota(p.begin(), p.end(), 0);
}
int find(int x){
return p[x] == x ? x : p[x] = find(p[x]);
}
void unite(int a, int b){
a = find(a); b = find(b);
if(a != b) p[b] = a;
}
};
static inline long long pack_pair(int a, int b){
// pack two ints into a 64-bit key
return ( (long long)a << 32 ) ^ (unsigned long long)b;
}
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 = (int)X.size();
int Q = (int)S.size();
vector<vector<int>> g(N+1);
for(int i=0;i<M;i++){
int x = X[i], y = Y[i];
g[x].push_back(y);
g[y].push_back(x);
}
DSU dsuH(N);
vector<int> compH(N+1);
vector<char> active(N+1, 0);
for(int v = N; v >= 1; --v){
active[v] = 1;
for(int nx : g[v]) if(active[nx]) dsuH.unite(v, nx);
compH[v] = dsuH.find(v);
}
DSU dsuW(N);
fill(active.begin(), active.end(), 0);
vector<int> compW(N+1);
for(int v = 1; v <= N; ++v){
active[v] = 1;
for(int nx : g[v]) if(active[nx]) dsuW.unite(v, nx);
compW[v] = dsuW.find(v);
}
unordered_map<long long,int> mp;
mp.reserve(N*2);
vector<int> id(N+1, 0);
int idCnt = 0;
for(int v=1; v<=N; ++v){
long long key = pack_pair(compH[v], compW[v]);
auto it = mp.find(key);
if(it == mp.end()){
++idCnt;
mp.emplace(key, idCnt);
id[v] = idCnt;
} else {
id[v] = it->second;
}
}
vector<vector<int>> pos(idCnt+1);
for(int v=1; v<=N; ++v) pos[id[v]].push_back(v);
for(int i=1;i<=idCnt;i++) sort(pos[i].begin(), pos[i].end());
vector<int> ans(Q, 0);
for(int i=0;i<Q;i++){
int s = S[i], e = E[i], l = L[i], r = R[i];
if(!(l+1 < r)){ // no valid T exists
ans[i] = 0;
continue;
}
long long key = pack_pair(compH[s], compW[e]);
auto it = mp.find(key);
if(it == mp.end()){
ans[i] = 0;
continue;
}
int myId = it->second;
auto &vec = pos[myId];
// find smallest position >= l+1
auto it2 = lower_bound(vec.begin(), vec.end(), l+1);
if(it2 != vec.end() && *it2 < r) ans[i] = 1;
else ans[i] = 0;
}
return ans;
}
