#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N=4e5+5;
const int oo=1e9+1;
int ori_n,ori_m,ori_request,n,m,request,x,y,u,v;
bool visited[N][2];
vector <int> Xvect,Yvect,Svect,Evect,Lvect,Rvect,adj[N],X,Y,S,E,L,R,ans;
queue <int> q;
namespace sub1
{
bool bfs(int start,int goal,int Left,int Right)
{
while (!q.empty()) q.pop();
for (int i=0;i<n;i++)
visited[i][0]=visited[i][1]=false;
visited[start][0]=true;
q.push(start);
while (!q.empty())
{
u=q.front();
q.pop();
if (u<n)
{
if (Left<=u and u<=Right)
{
visited[u][1]=true;
q.push(u+n);
}
for (int v:adj[u])
if (Left<=v and !visited[v][0])
{
visited[v][0]=true;
q.push(v);
}
}
else
{
u-=n;
for (int v:adj[u])
if (v<=Right and !visited[v][1])
{
visited[v][1]=true;
q.push(v+n);
}
}
}
return visited[goal][1];
}
}
namespace sub3
{
int timer;
int id[N],vt[N],tmiL[4*N],tmaR[4*N];
void dfs_reid(int u,int par)
{
id[u]=timer;
vt[timer]=u;
timer++;
for (int v:adj[u])
if (v!=par)
dfs_reid(v,u);
}
void build(int id,int l,int r)
{
if (l==r)
{
tmiL[id]=tmaR[id]=vt[l];
return;
}
int m=(l+r)/2;
build(id*2,l,m);
build(id*2+1,m+1,r);
tmiL[id]=min(tmiL[id*2],tmiL[id*2+1]);
tmaR[id]=max(tmaR[id*2],tmaR[id*2+1]);
}
int getLeft(int id,int l,int r)
{
if (u>r or v<l) return oo;
if (u<=l and v>=r) return tmiL[id];
int m=(l+r)/2;
return min(getLeft(id*2,l,m),getLeft(id*2+1,m+1,r));
}
int getRight(int id,int l,int r)
{
if (u>r or v<l) return -oo;
if (u<=l and v>=r) return tmaR[id];
int m=(l+r)/2;
return max(getRight(id*2,l,m),getRight(id*2+1,m+1,r));
}
vector <int> solve()
{
vector <int> res;
res.clear();
timer=0;
for (int i=0;i<n;i++)
if (adj[i].size()==1)
{
dfs_reid(i,-1);
break;
}
build(1,0,n-1);
for (int i=0;i<request;i++)
{
S[i]=id[S[i]];
E[i]=id[E[i]];
}
int l,r,mid,save_L,save_R;
for (int i=0;i<request;i++)
if (S[i]<E[i])
{
l=S[i];
r=E[i];
save_L=S[i];
while (l<=r)
{
mid=(l+r)/2;
u=S[i];
v=mid;
if (getLeft(1,0,n-1)>=L[i])
{
save_L=mid;
l=mid+1;
}
else r=mid-1;
}
l=S[i];
r=E[i];
save_R=E[i];
while (l<=r)
{
mid=(l+r)/2;
u=mid;
v=E[i];
if (getRight(1,0,n-1)<=R[i])
{
save_R=mid;
r=mid-1;
}
else l=mid+1;
}
res.push_back(save_L>=save_R);
}
else
{
l=E[i];
r=S[i];
save_L=S[i];
while (l<=r)
{
mid=(l+r)/2;
u=mid;
v=S[i];
if (getLeft(1,0,n-1)>=L[i])
{
save_L=mid;
r=mid-1;
}
else l=mid+1;
}
l=E[i];
r=S[i];
save_R=E[i];
while (l<=r)
{
mid=(l+r)/2;
u=E[i];
v=mid;
if (getRight(1,0,n-1)<=R[i])
{
save_R=mid;
l=mid+1;
}
else r=mid-1;
}
res.push_back(save_R>=save_L);
}
return res;
}
}
vector <int> check_validity(int originN,vector <int> originX,vector <int> originY,vector <int> originS,vector <int> originE,vector <int> originL,vector <int> originR)
{
n=originN;
m=originX.size();
request=originS.size();
X=originX;
Y=originY;
for (int i=0;i<m;i++)
{
x=X[i];
y=Y[i];
adj[x].push_back(y);
adj[y].push_back(x);
}
S=originS;
E=originE;
L=originL;
R=originR;
if (m==n-1)
{
bool ok=true;
for (int i=0;i<n;i++)
if (adj[i].size()>2)
{
ok=false;
break;
}
if (ok) return sub3::solve();
}
vector <int> res;
res.clear();
for (int i=0;i<request;i++)
res.push_back(sub1::bfs(S[i],E[i],L[i],R[i]));
return res;
}
