#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x.size())
#define pb push_back
#define fi first
#define se second
typedef vector<int> v;
typedef pair<int,int> ii;
const int MX = 200002;
const int INF = (int)(1e9);
v vec[MX];
bool vis[MX][2];
int val[MX],id[MX],idx;
ii st[4*MX];
void build(int node,int l,int r){
if(l==r){
st[node]={val[l],val[l]};
return;
}
int med=(l+r)>>1;
build(node*2,l,med),build(node*2+1,med+1,r);
st[node]={min(st[node*2].fi,st[node*2+1].fi),max(st[node*2].se,st[node*2+1].se)};
}
ii query(int node,int l,int r,int i,int j){
if(l>j || r<i)
return {INF,-1};
if(l>=i && r<=j)return st[node];
int med=(l+r)>>1;
ii q=query(node*2,l,med,i,j),q2=query(node*2+1,med+1,r,i,j);
return {min(q.fi,q2.fi),max(q.se,q2.se)};
}
int gimme_r(int node,int l,int r,int i,int j,int R){
if(l>j || r<i)return -1;
if(l>=i && r<=j){
if(st[node].se<=R)return -1;
while(l!=r){
int med=(l+r)>>1;
if(st[node*2+1].se>R)
l=med+1,node=node*2+1;
else r=med,node*=2;
}
return l;
}
int med=(l+r)>>1;
int q=gimme_r(node*2+1,med+1,r,i,j,R);
if(q!=-1)return q;
return gimme_r(node*2,l,med,i,j,R);
}
int gimme_l(int node,int l,int r,int i,int j,int R){
if(l>j || r<i)return -1;
if(l>=i && r<=j){
if(st[node].se<=R)return -1;
while(l!=r){
int med=(l+r)>>1;
if(st[node*2].se>R)
r=med,node*=2;
else l=med+1,node=node*2+1;
}
return l;
}
int med=(l+r)>>1;
int q=gimme_l(node*2,l,med,i,j,R);
if(q!=-1)return q;
return gimme_l(node*2+1,med+1,r,i,j,R);
}
vector<int> check_validity(int N, v X, v Y,v S, v E,v L, v R) {
int Q = sz(S);
v A(Q);
for (int i = 0; i < sz(X); ++i)
{
vec[X[i]].pb(Y[i]);
vec[Y[i]].pb(X[i]);
}
if(N<=3000){
for (int i = 0; i < Q; ++i)
{
if(i)for (int j = 0; j < N; ++j)
vis[j][0]=vis[j][1]=0;
queue<ii> q;
q.push({S[i],0});
vis[S[i]][0]=1;
while(!q.empty()){
ii f=q.front();
q.pop();
if(f.fi==E[i]){
if(f.se || ((S[i]>=L[i]) && (S[i]<=R[i]))){
A[i]=1;break;
}
}
if(f.fi>R[i])assert(!f.se);
if(f.fi<L[i])assert(f.se);
if((!f.se) && (f.fi>=L[i]) && (f.fi<=R[i]) && !vis[f.fi][1]){
vis[f.fi][1]=1;
q.push({f.fi,1});
}
for(auto it:vec[f.fi]){
if(vis[it][f.se])continue;
if((!f.se && it>=L[i]) || (f.se && it<=R[i])){
vis[it][f.se]=1;
q.push({it,f.se});
}
}
}
}
}
else{
int node=-1,p=-1,a;
ii h;
for (int i = 0; i < N; ++i)
if(sz(vec[i])==1){
node=i;
break;
}
assert(node!=-1);
while(1){
id[node]=idx,val[idx++]=node;
int cnt=0;
for(auto it:vec[node])
if(it!=p){p=node,node=it,cnt++;break;}
if(!cnt)break;
}
build(1,0,N-1);
for (int i = 0; i < Q; ++i)
{
if(id[S[i]]<id[E[i]]){
a=gimme_r(1,0,N-1,id[S[i]],id[E[i]],R[i]);
if((a==-1) && (S[i]>=L[i]))A[i]=1;
else if(a!=-1 && a!=id[E[i]]){
assert(val[a]>R[i]);
h=query(1,0,N-1,id[S[i]],a);
if((h.fi>=L[i]) && (val[a+1]>=L[i]))A[i]=1;
}
}
else{
a=gimme_l(1,0,N-1,id[E[i]],id[S[i]],R[i]);
if((a==-1) && (S[i]>=L[i]))A[i]=1;
else if(a!=-1 && a!=id[E[i]]){
assert(val[a]>R[i]);
h=query(1,0,N-1,a,id[S[i]]);
if((h.fi>=L[i]) && (val[a-1]>=L[i]))A[i]=1;
}
}
}
}
return A;
}
