#include"werewolf.h"
#include<bits/stdc++.h>
//#include"grader.cpp"
#define V vector
using namespace std;
V<int>g[200005];
int pos[200005],logs[200005],spx[200005][18],spn[200005][18],used[200005];
bool flag;
int gt_mx(int l,int r){
int lev=logs[r-l+1];
return max(spx[l][lev],spx[r-(1<<lev)+1][lev]);
}
int gt_mn(int l,int r){
int lev=logs[r-l+1];
return min(spn[l][lev],spn[r-(1<<lev)+1][lev]);
}
bool check(int l,int r,int nl,int nr){
if(l>r)swap(l,r);
return gt_mn(l,r)>=nl&>_mx(l,r)<=nr;
}
void man(int v,int mx){
if(v<mx)return;
used[v]=1;
for(auto to:g[v])if(!used[to]&&to>=mx)man(to,mx);
}
void wolf(int v,int mx) {
if(v>mx)return;
if(used[v]||flag){
flag=1;
return;
}
used[v]=2;
for(auto to:g[v])if(used[to]!=2&&to<=mx)wolf(to,mx);
}
V<int>check_validity(int n,V<int>x,V<int>y,V<int>S,V<int>E,V<int>L,V<int>R){
V<int>res;
int root,i,j;
for(i=2;i<=n;i++)logs[i]=logs[i>>1]+1;
for(i=0;i<x.size();i++){
x[i]++;
y[i]++;
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
if(n<3001&&x.size()<6001&&S.size()<3001){
for(i=0;i<S.size();i++){
flag=0;
fill(used+1,used+1+n,0);
man(S[i]+1,L[i]+1);
wolf(E[i]+1,R[i]+1);
res.push_back(flag);
}
return res;
}
for(i=1;i<=n;i++)if(g[i].size()==1)root=i;
spx[1][0]=root;
spn[1][0]=root;
pos[root]=1;
int p=root;
for(i=2;i<=n;i++){
if(g[root][0]!=p){
p=root;
root=g[root][0];
}else{
p=root;
root=g[root][1];
}
spx[i][0]=root;
spn[i][0]=root;
pos[root]=i;
}
for(j=1;j<18;j++){
for(i=1;i+(1<<j)-1<=n;i++)spn[i][j]=min(spn[i][j-1],spn[i+(1<<(j-1))][j-1]);
for(i=1;i+(1<<j)-1<=n;i++)spx[i][j]=max(spx[i][j-1],spx[i+(1<<(j-1))][j-1]);
}
for(int i=0;i<S.size();i++){
int l=pos[S[i]+1],r=pos[E[i]+1],s=L[i]+1,e=R[i]+1;
if(l<=r){
int mxl=n,mnr=1;
while(l<mxl){
int mid=(l+mxl+1)>>1;
if(check(pos[S[i]+1],mid,s,n))l=mid;
else mxl=mid-1;
}
while(mnr<r){
int mid=(mnr+r)>>1;
if(check(mid,pos[E[i]+1],1,e))r=mid;
else mnr=mid+1;
}
res.push_back(mxl>=mnr);
}else{
swap(l,r);
int mxl=n,mnr=1;
while(l<mxl){
int mid=(l+mxl+1)>>1;
if(check(pos[E[i]+1],mid,1,e))l=mid;
else mxl=mid-1;
}
while(mnr<r){
int mid=(mnr+r)>>1;
if(check(mid,pos[S[i]+1],s,n))r=mid;
else mnr=mid+1;
}
res.push_back(mxl>=mnr);
}
}
return res;
}
/*
10 9 10
6 7
1 5
8 0
2 9
9 4
2 7
8 5
6 0
3 4
4 9 0 9
8 1 8 9
1 8 1 8
8 3 5 5
8 9 3 9
0 1 0 2
9 0 6 6
1 7 1 8
9 4 5 6
9 5 0 9
/*
1
1
1
0
1
1
0
1
0
1
*/
