#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5+10;
const int INF = 0x3f3f3f3f;
int pai[2][MAXN], peso[2][MAXN];
int find(int tipo, int x){ return (pai[tipo][x]==x ? x : pai[tipo][x]=find(tipo, pai[tipo][x])); }
void join(int tipo, int a, int b){
a=find(tipo, a);
b=find(tipo, b);
if(a==b) return;
if(peso[tipo][a]>peso[tipo][b]) swap(a, b);
pai[tipo][a]=b;
peso[tipo][b]=max(peso[tipo][b], peso[tipo][a]+1);
}
int conv[MAXN], rev[MAXN];
vector<int> adj[MAXN];
void dfs(int ver, int val){
conv[val]=ver;
rev[ver]=val;
for(auto u : adj[ver]){
if(rev[u]!=-1) continue;
dfs(u, val+1);
}
}
int st[2][20][MAXN], lg[MAXN];
void build(int n){
lg[0]=lg[1]=0;
for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
for(int i=0;i<n;i++)
st[0][0][i]=st[1][0][i]=conv[i];
for(int i=1;i<=18;i++)
for(int j=0;j<n;j++)
st[0][i][j]=min(st[0][i-1][j], st[0][i-1][min(j+(1<<(i-1)), n)]);
for(int i=1;i<=18;i++)
for(int j=0;j<n;j++)
st[1][i][j]=max(st[1][i-1][j], st[1][i-1][min(j+(1<<(i-1)), n)]);
}
int getMx(int l, int r){
int curr=lg[r-l+1];
return max(st[1][curr][l], st[1][curr][r-(1<<curr)+1]);
}
int getMn(int l, int r){
int curr=lg[r-l+1];
return min(st[0][curr][l], st[0][curr][r-(1<<curr)+1]);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
int m=(int)X.size(), q=(int)L.size();
vector<int> ans(q);
if(N<=3000 && m<=6000 && q<=3000){
for(int i=0;i<q;i++){
for(int j=0;j<N;j++){
pai[0][j]=pai[1][j]=j;
peso[0][j]=peso[1][j]=0;
}
for(int j=0;j<m;j++){
if(max(X[j], Y[j])<=R[i]) join(1, X[j], Y[j]);
if(min(X[j], Y[j])>=L[i]) join(0, X[j], Y[j]);
}
ans[i]=0;
for(int j=0;j<N;j++){
if(find(0, S[i])==find(0, j) && find(1, E[i])==find(1, j)){
ans[i]=1;
break;
}
}
}
}
else{
memset(rev, -1, sizeof rev);
for(int i=0;i<m;i++){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
for(int i=0;i<N;i++){
if((int)adj[i].size()==1){
dfs(i, 0);
break;
}
}
build(N);
for(int i=0;i<q;i++){
int ini=rev[S[i]], fim=rev[E[i]];
if(ini==fim) ans[i]=1;
else if(ini<fim){
int lastH=-1;
if(getMx(ini, fim)>R[i]){
int low=ini, high=fim;
while(low<=high){
int mid=(low+high)>>1;
if(getMx(mid, fim)>R[i]){
lastH=mid;
low=mid+1;
}
else high=mid-1;
}
}
int lastW=INF;
if(getMn(ini, fim)<L[i]){
int low=ini, high=fim;
while(low<=high){
int mid=(low+high)>>1;
if(getMn(ini, mid)<L[i]){
lastW=mid;
high=mid-1;
}
else low=mid+1;
}
}
if(lastH>lastW || lastW==lastH+1) ans[i]=0;
else ans[i]=1;
}
else{
int lastH=INF;
if(getMx(fim, ini)>R[i]){
int low=fim, high=ini;
while(low<=high){
int mid=(low+high)>>1;
if(getMx(fim, mid)>R[i]){
lastH=mid;
high=mid-1;
}
else low=mid+1;
}
}
int lastW=-1;
if(getMn(fim, ini)<L[i]){
int low=fim, high=ini;
while(low<=high){
int mid=(low+high)>>1;
if(getMn(mid, ini)<L[i]){
lastW=mid;
low=mid+1;
}
else high=mid-1;
}
}
if(lastH<lastW || lastW==lastH-1) ans[i]=0;
else ans[i]=1;
}
}
}
return ans;
}
