#include <cstdio>
#include <cstdlib>
#include <vector>
#include<bits/stdc++.h>
#include "werewolf.h"
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
using namespace std;
int treemax[800001];
int treemin[800001];
void updatemax(int node,int start,int end,int idx,int val){
if(start==end){
treemax[node]=val;
}else{
int mid=(start+end)/2;
if(start<=idx and idx<=mid){
updatemax(2*node,start,mid,idx,val);
}else{
updatemax(2*node,mid+1,end,idx,val);
}
treemax[node]=max(treemax[2*node],treemax[2*node+1]);
}
}
void updatemin(int node,int start,int end,int idx,int val){
if(start==end){
treemin[node]=val;
}else{
int mid=(start+end)/2;
if(start<=idx and idx<=mid){
updatemin(2*node,start,mid,idx,val);
}else{
updatemin(2*node,mid+1,end,idx,val);
}
treemin[node]=min(treemin[2*node],treemin[2*node+1]);
}
}
int querymax(int node,int start,int end,int l,int r){
if(l>end or r<start){
return 0;
}
if(l<=start and end<=r){
return treemax[node];
}
int mid=(start+end)/2;
return max(querymax(2*node,start,mid,l,r),querymax(2*node+1,mid+1,end,l,r));
}
int querymin(int node,int start,int end,int l,int r){
if(l>end or r<start){
return 1e9;
}
if(l<=start and end<=r){
return treemin[node];
}
int mid=(start+end)/2;
return min(querymin(2*node,start,mid,l,r),querymin(2*node+1,mid+1,end,l,r));
}
std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
int q = S.size();
std::vector<int> A(q);
vector<int>adjl[n+1];
int m=X.size(); for(int i=0;i<m;i++){
adjl[X[i]].push_back(Y[i]);
adjl[Y[i]].push_back(X[i]);
}
if(n<=3000 and m<=6000 and q<=3000){
for (int i = 0; i < q; ++i) {
A[i] = 0;
int x=S[i];
int y=E[i];
int l=L[i];
int r=R[i];
int wolf[n+1];
int human[n+1];
for(int j=0;j<n;j++){
wolf[j]=0;
human[j]=0;
}
queue<int>q;
q.push(x);
human[x]++;
while(!q.empty()){
int a=q.front();
q.pop();
for(int j=0;j<adjl[a].size();j++){
if(human[adjl[a][j]]==0 and adjl[a][j]>=l){
human[adjl[a][j]]++;
q.push(adjl[a][j]);
}
}
}
q.push(y);
wolf[y]++;
while(!q.empty()){
int a=q.front();
q.pop();
for(int j=0;j<adjl[a].size();j++){
if(wolf[adjl[a][j]]==0 and adjl[a][j]<=r){
wolf[adjl[a][j]]++;
q.push(adjl[a][j]);
}
}
}
for(int j=0;j<n;j++){
if(human[j]>0 and wolf[j]>0){
A[i]++;
}
}
A[i]=min(A[i],1);
}
return A;
}else{
int loc[n]; int vis[n+1];
int value[n];
for(int i=0;i<n;i++){
vis[i]=0;
}
for(int i=0;i<n;i++){
if(adjl[i].size()==1){
int ro=0;
int t1=0;
int so=i;
while(t1==0){
loc[so]=ro;
value[ro]=so;
vis[so]++;
ro++;
int bro=0;
int so1=so;
for(int j=0;j<adjl[so1].size();j++){
if(vis[adjl[so1][j]]==0){
so=adjl[so1][j];
bro++;
break;
}
}
if(bro==0){
break;
}
}
break;
}
}
for(int i=0;i<n;i++){
updatemin(1,0,n-1,i,value[i]);
updatemax(1,0,n-1,i,value[i]);
}
for(int i=0;i<q;i++){
A[i] = 0;
int x=S[i];
int y=E[i];
int x1=loc[S[i]];
int y1=loc[E[i]];
int l1=L[i];
int r1=R[i];
int ans1=x;
int ans2=y;
int l=x1;
int r=n-1;
while(l<=r){
int mid=(l+r)/2;
int t=querymin(1,0,n-1,x1,mid);
if(t>=l){
ans1=max(ans1,mid);
l=mid+1;
}else{
r=mid-1;
}
}
l=0;
r=y1;
while(l<=r){
int mid=(l+r)/2;
int t=querymax(1,0,n-1,mid,y1);
if(t<=r){
ans2=min(ans2,mid);
r=mid-1;
}else{
l=mid+1;
}
}
if(ans1>=ans2){
A[i]++;
}
}
return A;
}
}
