#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;
}
};
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+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 for human ----------
DSU dsuH(N);
vector<int> compH(N+1);
vector<bool> active(N+1, false);
for(int v = N; v >= 1; v--){
active[v] = true;
for(int nxt : g[v]) if(active[nxt]){
dsuH.unite(v, nxt);
}
compH[v] = dsuH.find(v);
}
// ---------- DSU for wolf ----------
DSU dsuW(N);
fill(active.begin(), active.end(), false);
vector<int> compW(N+1);
for(int v = 1; v <= N; v++){
active[v] = true;
for(int nxt : g[v]) if(active[nxt]){
dsuW.unite(v, nxt);
}
compW[v] = dsuW.find(v);
}
// ---------- Build pairs ----------
vector<pair<int,int>> A(N+1);
for(int v=1; v<=N; v++){
A[v] = {compH[v], compW[v]};
}
vector<pair<pair<int,int>,int>> all;
for(int v=1; v<=N; v++){
all.push_back({A[v], v});
}
sort(all.begin(), all.end());
vector<int> id(N+1);
int idCnt = 0;
pair<int,int> last = {-1,-1};
for(auto &p : all){
if(p.first != last){
last = p.first;
idCnt++;
}
id[p.second] = idCnt;
}
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());
// ---------- Answer queries ----------
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];
int targetH = compH[s];
int targetW = compW[e];
pair<pair<int,int>,int> key = {{targetH, targetW}, -1};
auto it = lower_bound(all.begin(), all.end(), key,
[](auto &a, auto &b){ return a.first < b.first; }
);
if(it != all.end() && it->first == key.first){
int myId = id[it->second];
auto &vec = pos[myId];
auto it2 = lower_bound(vec.begin(), vec.end(), l+1);
if(it2 != vec.end() && *it2 < r){
ans[i] = 1;
}
}
}
return ans;
}
