#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const long long MAXN=400009;
int mas[MAXN];
vector<pair<int,int>> edg;
vector<int> A;
inline int min1(int a,int b)
{
if(a>b)return b;
return a;
}
inline int max1(int a,int b)
{
if(a<b)return b;
return a;
}
struct Fenwick
{
int fen[MAXN];
int lp2(int a)
{
return a&(-a);
}
void change(int a)
{
while(a<MAXN)
{
fen[a]++;
a+=lp2(a);
}
}
int getAns(int a)
{
int ans=0;
while(a>=0)
{
ans+=fen[a];
a-=lp2(a);
}
return ans;
}
int query(int l,int r)
{
return getAns(r)-getAns(l-1);
}
};
struct Tree
{
int eulT[MAXN];
int father[MAXN],fatherDSU[MAXN],nodeEdg[MAXN],dist[MAXN],posEul[MAXN];
int dp[MAXN][35];
int sons[MAXN][2];
pair<int,int> range[MAXN];
int N,curr;
int Lead(int a)
{
if(fatherDSU[a]==a)return a;
return fatherDSU[a]=Lead(fatherDSU[a]);
}
pair<int,int> dfs(int start,int d)
{
dist[start]=d;
if(start<=N)
{
posEul[start]=curr;
eulT[curr]=start;
range[start]={curr,curr};
curr++;
return range[start];
}
range[start]= {dfs(sons[start][0],d+1).first,dfs(sons[start][1],d+1).second};
return range[start];
}
long long f(int n,int p)
{
if(dp[n][p]!=0)return dp[n][p];
if(p==0)return father[n];
return dp[n][p]=f(f(n,p-1),p-1);
}
int lca(int a,int b)
{
if(dist[a]>dist[b])swap(a,b);
for(int i=0; i<30; i++)
{
if((dist[b]-dist[a])&(1LL<<i))b=f(b,i);
}
if(a==b)return a;
for(int i=30; i>=0; i--)
{
if(f(a,i)!=f(b,i))
{
a=f(a,i);
b=f(b,i);
}
}
return father[a];
}
pair<int,int> findRange(int n,int wei,bool big)
{
if(big)
{
for(int i=32;i>=0;i--)
{
if(nodeEdg[f(n,i)]<=wei)n=f(n,i);
}
}
else
{
for(int i=32;i>=0;i--)
{
if(nodeEdg[f(n,i)]>=wei)n=f(n,i);
}
}
return range[n];
}
void build(int n,vector<pair<int,int>> edg,bool big)
{
N=n;
curr=N+1;
for(int i=1;i<=N;i++)
{
nodeEdg[i]=i;
fatherDSU[i]=i;
}
for(auto i:edg)
{
if(Lead(i.first)==Lead(i.second))continue;
if(big)nodeEdg[curr]=max1(nodeEdg[Lead(i.first)],nodeEdg[Lead(i.second)]);
else nodeEdg[curr]=min1(nodeEdg[Lead(i.first)],nodeEdg[Lead(i.second)]);
sons[curr][0]=Lead(i.first);
sons[curr][1]=Lead(i.second);
father[curr]=curr;
fatherDSU[curr]=curr;
father[Lead(i.first)]=curr;
fatherDSU[Lead(i.first)]=curr;
father[Lead(i.second)]=curr;
fatherDSU[Lead(i.second)]=curr;
curr++;
}
curr=1;
dfs(2*N-1,0);
}
};
Tree treeMax,treeMin;
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=X.size(),Q=S.size();
pair<int,int> x,y;
for(int i=0;i<M;i++)
{
X[i]++;
Y[i]++;
if(X[i]<Y[i])swap(X[i],Y[i]);
edg.push_back({X[i],Y[i]});
}
sort(edg.begin(),edg.end());
treeMax.build(N,edg,1);
for(int i=0;i<M;i++)
{
swap(edg[i].first,edg[i].second);
}
sort(edg.begin(),edg.end());
reverse(edg.begin(),edg.end());
treeMin.build(N,edg,0);
for(int i=1;i<=N;i++)mas[i]=treeMax.posEul[treeMin.eulT[i]];
for(int i=0;i<Q;i++)
{
S[i]++;
E[i]++;
L[i]++;
R[i]++;
if(S[i]<L[i]||E[i]>R[i])
{
A.push_back(0);
continue;
}
x=treeMin.findRange(S[i],L[i],0);
y=treeMax.findRange(E[i],R[i],1);
bool ans=0;
for(int i=y.first;i<=y.second;i++)
{
ans=ans||(mas[i]>=x.first&&mas[i]<=x.second);
}
A.push_back(ans);
}
return A;
}
