#include "bits/stdc++.h"
#include "werewolf.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int N = 200005;
const int INF = 1000000007;
vector<int> v[N];
vector<int> Hvis,Wvis,ar;
void create(int c,int p,int ind){
ar[ind]=c;
for(int x:v[c]){
if(x==p) continue;
create(x,c,ind+1);
}
}
void dfs_h(int c,int l){
if(Hvis[c]) return;
Hvis[c]=1;
for(int x:v[c]) if(x>=l) dfs_h(x,l);
}
void dfs_w(int c,int r){
if(Wvis[c]) return;
Wvis[c]=1;
for(int x:v[c]) if(x<=r) dfs_w(x,r);
}
struct SegT{
vector<int> mn,mx;
SegT(int _n){
mn.assign(4*_n+5,INF);
mx.assign(4*_n+5,-INF);
}
void build(int rt,int l,int r){
if(l==r){
mn[rt]=mx[rt]=ar[l];
return;
}
int m=(l+r)/2;
build(rt*2,l,m),build(rt*2+1,m+1,r);
mn[rt]=min(mn[rt*2],mn[rt*2+1]);
mx[rt]=max(mx[rt*2],mx[rt*2+1]);
}
int get_max(int rt,int l,int r,int gl,int gr){
if(l>=gl && r<=gr) return mx[rt];
if(r<gl || l>gr) return -INF;
int m=(l+r)/2;
return max(get_max(rt*2,l,m,gl,gr),get_max(rt*2+1,m+1,r,gl,gr));
}
int get_min(int rt,int l,int r,int gl,int gr){
if(l>=gl && r<=gr) return mn[rt];
if(r<gl || l>gr) return INF;
int m=(l+r)/2;
return min(get_min(rt*2,l,m,gl,gr),get_min(rt*2+1,m+1,r,gl,gr));
}
};
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 n=_N,m=sz(X),q=sz(L);
for(int i=0;i<m;i++){
int a=X[i],b=Y[i];
v[a].push_back(b);
v[b].push_back(a);
}
vector<int> res(q,0);
if(n<3005){
for(int i=0;i<q;i++){
int x=S[i],y=E[i],l=L[i],r=R[i];
Wvis.assign(n+5,0);
Hvis.assign(n+5,0);
dfs_h(x,l);
dfs_w(y,r);
bool ok=0;
for(int i=0;i<n;i++) if(Wvis[i] && Hvis[i]) ok=1;
res[i]=ok;
}
}
else{
ar.assign(n+5,0);
for(int i=0;i<n;i++){
if(sz(v[i])==1){
create(i,-1,0);
break;
}
}
SegT Seg(n+5);
Seg.build(1,0,n);
for(int i=0;i<q;i++){
int x=S[i],y=E[i],l=L[i],r=R[i];
if(x<y){
int ll = x , rr = n - 1;
while(ll<rr){
int mm = (ll+rr+1)/2;
if(Seg.get_min(1,0,n,x,mm)>=l) ll=mm;
else rr=mm-1;
}
int l2 = 0 , r2 = y;
while(l2<r2){
int m2 = (l2+r2)/2;
if(Seg.get_max(1,0,n,m2,y)<=r) r2=m2;
else l2=m2+1;
}
res[i] = (l2 <= ll);
}
else{
int ll = 0 , rr = x;
while(ll<rr){
int mm = (ll+rr)/2;
if(Seg.get_min(1,0,n,mm,x)>=l) rr=mm;
else ll=mm+1;
}
int l2 = y , r2 = n - 1;
while(l2<r2){
int m2 = (l2+r2+1)/2;
if(Seg.get_max(1,0,n,y,m2)<=r) l2=m2;
else r2=m2-1;
}
res[i] = (ll <= l2);
}
}
}
return res;
}
/*void _(){
int n,m,q;
cin >> n >> m >> q;
for(int i=0;i<m;i++){
int a,b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
while(q--){
int x,y,l,r;
cin >> x >> y >> l >> r;
Wvis.assign(n+5,0);
Hvis.assign(n+5,0);
dfs_h(x,l);
dfs_w(y,r);
bool ok=0;
for(int i=0;i<n;i++) if(Wvis[i] && Hvis[i]) ok=1;
cout << ok;
}
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/
