#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
namespace s{
vector<ll> g[3010];
bool vis[3010][2];
void dfs(ll x,ll l,ll r,bool dir){
if(not(l<=x&&x<=r))return;
if(vis[x][dir])return;
vis[x][dir]=1;
for(auto y:g[x]){
dfs(y,l,r,dir);
}
}
};
#define NN 200010
vector<ll> g[200010];
namespace segmi{
ll dat[2*NN];
void init(){
for(int i=0;i<2*NN;i++)dat[i]=1e17;
}
void upd(ll i,ll x){
i+=NN; dat[i]=x;
for(;i;i>>=1){
dat[i/2]=min(dat[i],dat[i^1]);
}
}
ll qry(ll l,ll r){
l+=NN,r+=NN+1;
ll res=1e17;
for(ll a=l,b=r;a<b;a>>=1,b>>=1){
if(a&1)chmin(res,dat[a++]);
if(b&1)chmin(res,dat[--b]);
}
return res;
}
};
namespace segma{
ll dat[2*NN];
void init(){
for(int i=0;i<2*NN;i++)dat[i]=-1e17;
}
void upd(ll i,ll x){
i+=NN; dat[i]=x;
for(;i;i>>=1){
dat[i/2]=max(dat[i],dat[i^1]);
}
}
ll qry(ll l,ll r){
l+=NN,r+=NN+1;
ll res=-1e17;
for(ll a=l,b=r;a<b;a>>=1,b>>=1){
if(a&1)chmax(res,dat[a++]);
if(b&1)chmax(res,dat[--b]);
}
return res;
}
};
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R){
if(N>3000){
for(int i=0;i<X.size();i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
ll arr[200010],id[200010];
ll st,nex;
for(int i=0;i<N;i++)if(g[i].size()==1)st=i;
arr[0]=st;
nex=g[st][0];
for(int i=1;i<N;i++){
arr[i]=nex;
if(g[nex][0]==arr[i-1]){
nex=g[nex][1];
}
else{
nex=g[nex][0];
}
}
for(int i=0;i<N;i++)id[arr[i]]=i;
segmi::init(); for(int i=0;i<N;i++)segmi::upd(i,arr[i]);
segma::init(); for(int i=0;i<N;i++)segma::upd(i,arr[i]);
vector<int> ans;
for(int q=0;q<S.size();q++){
ans.push_back(0);
ll l,r,mid;
if(id[S[q]]<id[E[q]]){
l=id[S[q]],r=N;
while(l<r-1){
mid=(l+r)>>1;
if(segmi::qry(id[S[q]],mid)>=L[q])l=mid;
else r=mid;
}
ll vs=l;
l=-1,r=id[E[q]];
while(l<r-1){
mid=(l+r)>>1;
if(segma::qry(mid,id[E[q]])<=R[q])r=mid;
else l=mid;
}
ll ve=r;
ans[q]=(vs>=ve);
}
else{
l=-1,r=id[S[q]];
while(l<r-1){
mid=(l+r)>>1;
if(segmi::qry(mid,id[S[q]])>=L[q])r=mid;
else l=mid;
}
ll vs=r;
l=id[E[q]],r=N;
while(l<r-1){
mid=(l+r)>>1;
if(segma::qry(id[E[q]],mid)<=R[q])l=mid;
else r=mid;
}
ll ve=l;
ans[q]=(vs<=ve);
}
}
return ans;
}
else{
for(int i=0;i<X.size();i++){
s::g[X[i]].push_back(Y[i]);
s::g[Y[i]].push_back(X[i]);
}
vector<int> ans;
for(int q=0;q<S.size();q++){
for(int i=0;i<N;i++)s::vis[i][0]=s::vis[i][1]=0;
s::dfs(S[q],L[q],N-1,0);
s::dfs(E[q],0,R[q],1);
ans.push_back(0);
for(int i=0;i<N;i++){
if(s::vis[i][0]==1&&s::vis[i][1]==1){
ans[q]=1;
}
}
}
return ans;
}
}/*
int main(){
return 0;
}*/
