#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>adj[200005];
int a[200005],pos[200005];
int last=0,cnt=0;
void dfs(int i,int p,int t){
pos[i]=cnt;
if(t==2) a[cnt++]=i;
last=i;
for(int j:adj[i]){
if(j!=p) dfs(j,i,t);
}
}
int st1[200005][20],st2[200005][20];
void build(){
for(int i=0;i<cnt;i++){
st1[i][0]=st2[i][0]=a[i];
}
for(int j=1;j<19;j++){
for(int i=0;i<=cnt-(1<<j);i++){
st1[i][j]=min(st1[i][j-1],st1[i+(1<<(j-1))][j-1]);
st2[i][j]=max(st2[i][j-1],st2[i+(1<<(j-1))][j-1]);
}
}
}
int query(int l,int r,int t){
if(l>r) swap(l,r);
int k=log2(r-l+1);
if(t==1) return min(st1[l][k],st1[r-(1<<k)+1][k]);
else return max(st2[l][k],st2[r-(1<<k)+1][k]);
}
int check(int s,int e,int m,int l,int r){
int q1=query(s,m,1),q2=query(m,e,2);
if(q1>=l&&q2<=r) return 0; //GOOD
else if(q1>=l) return 1; //MOVE RIGHT
else if(q2<=r) return 2; //MOVE LEFT
else return 3; //BAD
}
bool vis[3005];
void dfs2(int i,int m,int t){
vis[i]=true;
for(int j:adj[i]){
if(vis[j]) continue;
if(t==1&&j<m) continue;
if(t==2&&j>m) continue;
dfs2(j,m,t);
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
for(int i=0;i<X.size();i++){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
if(N>3000){
dfs(0,-1,1);
dfs(last,-1,2);
vector<int>ans;
build();
for(int i=0;i<S.size();i++){
int s=pos[S[i]],e=pos[E[i]],l=L[i],r=R[i];
int ll=s,rr=e;
if(s<e){
while(ll<rr){
int mm=(ll+rr)/2;
//cout<<mm<<" ";
int ch=check(s,e,mm,l,r);
if(ch==0){
ans.push_back(1);
goto hell;
}
else if(ch==3){
ans.push_back(0);
goto hell;
}
else if(ch==1) ll=mm+1;
else rr=mm-1;
if(ll>rr){
ans.push_back(0);
goto hell;
}
}
}
else{
while(ll>rr){
int mm=(ll+rr)/2;
int ch=check(s,e,mm,l,r);
if(ch==0){
ans.push_back(1);
goto hell;
}
else if(ch==3){
ans.push_back(0);
goto hell;
}
else if(ch==1) ll=mm-1;
else rr=mm+1;
if(ll<rr){
ans.push_back(0);
goto hell;
}
}
}
if(check(s,e,ll,l,r)==0){
ans.push_back(1);
}
else ans.push_back(0);
hell:;
}
return ans;
}
else{
vector<int>ans;
for(int i=0;i<S.size();i++){
int s=S[i],e=E[i],l=L[i],r=R[i];
for(int j=l;j<=r;j++){
memset(vis,false,sizeof vis);
dfs2(j,l,1);
if(!vis[s]) continue;
memset(vis,false,sizeof vis);
dfs2(j,r,2);
if(!vis[e]) continue;
ans.push_back(1);
goto hell2;
}
ans.push_back(0);
hell2:;
}
return ans;
}
}
