#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
int ok[3][200555];
vector <int> v[200555];
vector <int> new_old;
int old_new[200555];
int f(int N, int s, int e, int l, int r){
queue <int> q;
memset(ok, 0, sizeof(ok));
if(l<=s){
ok[1][s]=1;
q.push(1);
q.push(s);
}
if(e<=r){
ok[0][e]=1;
q.push(0);
q.push(e);
}
while(!q.empty()){
int type=q.front(); q.pop();
int x=q.front(); q.pop();
//rintf("%d %d\n", type, x);
for(int i=0;i<v[x].size();i++){
if(type==0){
if(v[x][i]<=r&&ok[type][v[x][i]]==0){
ok[type][v[x][i]]=1;
q.push(type);
q.push(v[x][i]);
}
}
else{
if(l<=v[x][i]&&ok[type][v[x][i]]==0){
ok[type][v[x][i]]=1;
q.push(type);
q.push(v[x][i]);
}
}
}
}
for(int i=0;i<N;i++)
if(ok[0][i]&&ok[1][i])return 1;
return 0;
}
int nn;
int dp_min[600555];
int dp_max[600555];
void Cal_DP(int N){
for(nn=1;nn<N;nn*=2);
for(int i=nn;i<2*nn;i++){
dp_min[i]=N+5;
dp_max[i]=-1;
if(i-nn<N)dp_min[i]=dp_max[i]=new_old[i-nn];
}
for(int i=nn-1;i;i--){
dp_min[i]=min(dp_min[2*i], dp_min[2*i+1]);
dp_max[i]=max(dp_max[2*i], dp_max[2*i+1]);
}
}
void Apple(int N){
int vis[200555];
memset(vis, 0, sizeof(vis));
int start;
for(start=0;start<N;start++)
if(v[start].size()==1)
break;
for(int i=0;i<=N;i++){
vis[start]=1;
new_old.push_back(start);
old_new[start]=i;
for(int j=0;j<v[start].size();j++)
if(!vis[j])
start=j;
}
}
int find_min(int i, int c_l, int c_r, int input_l, int input_r){
if(input_l<=c_l&&c_r<=input_r)return dp_min[i];
if(input_r<c_l||c_r<input_l)return 987654321;
int res=987654321;
int mid=(c_l+c_r)/2;
if(input_l<=c_r)res=min(res, f(2*i, c_l, mid, input_l, input_r));
if(c_l<=input_r)res=min(res, f(2*i+1, mid+1, c_r, input_l, input_r));
return res;
}
int find_max(int i, int c_l, int c_r, int input_l, int input_r){
if(input_l<=c_l&&c_r<=input_r)return dp_max[i];
if(input_r<c_l||c_r<input_l)return -1;
int res=-1;
int mid=(c_l+c_r)/2;
if(input_l<=c_r)res=max(res, f(2*i, c_l, mid, input_l, input_r));
if(c_l<=input_r)res=max(res, f(2*i+1, mid+1, c_r, input_l, input_r));
return res;
}
int g(int N, int s, int e, int l, int r){
if(s<l)return 0;
if(r<e)return 0;
int l1=old_new[s], r1=N-1, man_max=old_new[s];
while(l1<=r1){
int mid=(l1+r1)/2;
int z=find_min(1, 1, nn, old_new[s]+1, mid+1);
if(l<=z)man_max=max(man_max, mid), l1=mid+1;
else r1=mid-1;
}
int l2=0, r2=old_new[s], man_min=old_new[s];
while(l2<=r2){
int mid=(l2+r2)/2;
int z=find_min(1, 1, nn, mid+1, old_new[s]+1);
if(l<=z)man_min=max(man_min, mid), r2=mid-1;
else l2=mid+1;
}
int f1=man_min, f2=man_max;
l1=old_new[e], r1=N-1, man_max=old_new[e];
while(l1<=r1){
int mid=(l1+r1)/2;
int z=find_max(1, 1, nn, old_new[e]+1, mid+1);
if(r>=z)man_max=max(man_max, mid), l1=mid+1;
else r1=mid-1;
}
l2=0, r2=old_new[e], man_min=old_new[e];
while(l2<=r2){
int mid=(l2+r2)/2;
int z=find_min(1, 1, nn, mid+1, old_new[e]+1);
if(r>=z)man_min=max(man_min, mid), r2=mid-1;
else l2=mid+1;
}
int f3=man_min, f4=man_max;
if(f4<f1||f2<f3)return 0;
return 1;
}
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();
for(int i=0;i<X.size();i++){
v[X[i]].push_back(Y[i]);
v[Y[i]].push_back(X[i]);
}
vector<int> A(Q);
if(N<=3000&&X.size()<=6000&Q<=3000){
for (int i = 0; i < Q; ++i)
A[i] = f(N, S[i], E[i], L[i], R[i]);
return A;
}
Apple(N);
Cal_DP(N);
for(int i=0;i<Q;i++){
A[i]=g(N, S[i], E[i], L[i], R[i]);
}
return A;
}
