#pragma GCC optimize("O3")
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
#define INF (int)(1e9)
vector<vector<int> > vec;
int A[200005],idx=0,to_id[200005];
ii st[800005];
bool vis[200005];
void build(int node,int l,int r){
if(l==r){
st[node]=ii(A[l],A[l]);
return ;
}
int med=((l+r)>>1);
build(node<<1,l,med),build((node<<1)+1,med+1,r);
st[node].fi=min(st[node<<1].fi,st[(node<<1)+1].fi);
st[node].se=max(st[node<<1].se,st[(node<<1)+1].se);
}
ii query(int node,int l,int r,int i,int j){
if(l>j||r<i)
return ii(INF,-1);
if(l>=i&&r<=j)
return st[node];
int med=((l+r)>>1);
ii q1=query(node<<1,l,med,i,j),q2=query((node<<1)+1,med+1,r,i,j);
return ii(min(q1.fi,q2.fi),max(q1.se,q2.se));
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
vec.resize(N);
for (int i = 0; i < X.size(); ++i)
{
vec[X[i]].pb(Y[i]);
vec[Y[i]].pb(X[i]);
}
int start=0;
for (int i = 0; i < N; ++i)
if(vec[i].size()==1){
start=i;
break;
}
queue<int> AA;
AA.push(start);
vis[start]=1;
while(!AA.empty()){
int front=AA.front();
A[idx]=front;
to_id[front]=idx++;
AA.pop();
for(auto child:vec[front])
if(!vis[child])
vis[child]=1,AA.push(child);
}
build(1,0,idx);
int Q = S.size();
vector<int> res(Q);
fill(res.begin(),res.end(),0);
for (int i = 0; i < Q; ++i) {
if(S[i]==E[i]){
if(S[i]<=R[i]&&S[i]>=L[i])res[i]=1;
else res[i]=0;
continue;
}
if(S[i]<L[i]||E[i]>R[i]){res[i]=0;continue;}
if(to_id[S[i]]<to_id[E[i]]){
//cerr<<1<<" ";
int l=to_id[S[i]],r=to_id[E[i]];
while(l<=r){
int med=((l+r)>>1);
if(med!=to_id[S[i]]){
ii q=query(1,0,idx,to_id[S[i]],med-1);
//cerr<<q.fi<<" "<<q.se<<"\n";
if(q.fi<L[i]){r=med-1;continue;}
}
if(med!=to_id[E[i]]){
ii q=query(1,0,idx,med+1,to_id[E[i]]);
//cerr<<q.fi<<" "<<q.se<<"\n";
if(q.se>R[i]){l=med+1;continue;}
}
if(A[med]<=R[i]&&A[med]>=L[i])res[i]=1;
else if(A[med]>=L[i]){
if(med==(E[i]))res[i]=0;
else if(A[med+1]<=R[i]&&A[med+1]>=L[i])res[i]=1;
else res[i]=0;
}
else if(A[med]<=R[i]){
if(med==S[i])res[i]=0;
else if(A[med-1]<=R[i]&&A[med-1]>=L[i])res[i]=1;
else res[i]=0;
}
break;
}
}
else{
//cerr<<2<<" ";
int l=to_id[E[i]],r=to_id[S[i]];
while(l<=r){
int med=((l+r)>>1);
if(med!=to_id[E[i]]){
ii q=query(1,0,idx,to_id[E[i]],med-1);
if(q.se>R[i]){r=med-1;continue;}
}
if(med!=to_id[S[i]]){
ii q=query(1,0,idx,med+1,to_id[S[i]]);
if(q.fi<L[i]){l=med+1;continue;}
}
//cerr<<med<<"-----\n";
if(A[med]<=R[i]&&A[med]>=L[i])res[i]=1;
else if(A[med]<=R[i]){
if(med==(S[i]))res[i]=0;
else if(A[med+1]<=R[i]&&A[med+1]>=L[i])res[i]=1;
else res[i]=0;
}
else if(A[med]>=L[i]){
if(med==E[i])res[i]=0;
else if(A[med-1]<=R[i]&&A[med-1]>=L[i])res[i]=1;
else res[i]=0;
}
break;
}
}
//cerr<<res[i]<<"\n";
}
return res;
}
