#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<int> > G;
int vish[5000];
int visw[5000];
int vis[400000];
int tree[1000000];
int tree1[1000000];
int a,b;
int v[400000];
int k=0;
int h,h1;
map<ll,ll> mp;
void init1(int node,int l,int r){
if(l==r) tree[node]=v[l];
else{
int mi=(l+r)/2;
init1(2*node,l,mi);
init1(2*node+1,mi+1,r);
tree[node]=max(tree[2*node],tree[2*node+1]);
}
}
int query1(int x,int y,int node,int l,int r){
if(r<x or l>y ) return -10000;
if(x<=l and r<=y){
return tree[node];
}
else{
int mi=(l+r)/2;
return max(query1(x,y,2*node,l,mi),query1(x,y,2*node+1,mi+1,r));
}
}
void init2(int node,int l,int r){
if(l==r) tree1[node]=v[l];
else{
int mi=(l+r)/2;
init2(2*node,l,mi);
init2(2*node+1,mi+1,r);
tree1[node]=min(tree1[2*node],tree1[2*node+1]);
}
}
int query2(int x,int y,int node,int l,int r){
if(r<x or l>y ) return 4000000;
if(x<=l and r<=y){
return tree1[node];
}
else{
int mi=(l+r)/2;
return min(query2(x,y,2*node,l,mi),query2(x,y,2*node+1,mi+1,r));
}
}
void dfs(int x){
v[k]=x;
k++;
vis[x]=1;
int tam1=G[x].size();
for(int i=0;i<tam1;i++){
int u=G[x][i];
if(vis[u]==0){
dfs(u);
}
}
}
void dfsh(int x){
vish[x]=1;
int taml=G[x].size();
for(int i=0;i<taml;i++){
int u=G[x][i];
if(vish[u]==0 and u>=a){
dfsh(u);
//cout<<x<<" "<<1<<endl;
}
}
}
void dfsw(int x){
visw[x]=1;
int taml=G[x].size();
for(int i=0;i<taml;i++){
int u=G[x][i];
if(visw[u]!=1 and u<=b){
dfsw(u);
//cout<<x<<" "<<2<<endl;
}
}
}
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();
G.clear();
int tam=X.size();
G.assign(tam+1,vector<int>());
for(int i=0;i<tam;i++){
G[X[i]].push_back(Y[i]);
G[Y[i]].push_back(X[i]);
}
//int c1=0;
//int c2=0;
int d1;
for(int i=0;i<tam;i++){
if(G[i].size()==1){
d1=i;
break;
}
}
std::vector<int> A(Q);
if(N<=3000 and Q<=3000){
for (int i = 0; i < Q; ++i) {
memset(vish, 0, sizeof vish);
memset(visw, 0,sizeof visw);
a=L[i];
b=R[i];
dfsh(S[i]);
dfsw(E[i]);
int sw=0;
for(int j=0;j<N;j++){
if(vish[j]==1 and visw[j]==1){
sw=1;
break;
}
}
if(sw==1){
A[i]=1;
}
else{
A[i]=0;
}
}
return A;
}
memset(vis, 0, sizeof vis);
dfs(d1);
for(int i=0;i<N;i++){
mp[v[i]]=i;
//cout<<v[i]<<" ";
}
// cout<<endl;
init1(0,0,N-1);
init2(0,0,N-1);
for (int i=0;i<Q;++i) {
//int sw=0;
int a=min(mp[S[i]],mp[E[i]]);
int b=max(mp[S[i]],mp[E[i]]);
if(S[i]<L[i] or E[i]>R[i]){
A[i]=0;
continue;
}
int low=a,hi=b,mid;
while(hi-low>1){
mid=(low+hi)/2;
int minimo=query2(low,mid,0,0,N-1);
if(minimo>=L[i])low=mid;
else hi=mid;
}
//cout<<1<<endl;
int maximo=query1(hi,b,0,0,N-1);
if(maximo<=R[i]){
A[i]=1;
}
else{
A[i]=0;
}
}
return A;
}
