#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int N=4e5+5;
const int K=22;
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;
namespace sub4
{
int h,tour;
int par[N][2],bit[N],arr[N][2],tin[N][2],tout[N][2],root[2],p[N][K][2];
vector <int> adj[N][2],g[N];
vector <pii> query[N];
int acs(int u,int t)
{
if (par[u][t]<0) return u;
return par[u][t]=acs(par[u][t],t);
}
void join(int u,int v,int t)
{
int x=acs(u,t);
int y=acs(v,t);
if (x!=y)
{
par[x][t]+=par[y][t];
par[y][t]=x;
root[t]=x;
adj[x][t].push_back(y);
}
}
void dfs(int u,int t)
{
tin[u][t]=++tour;
arr[tour][t]=u;
for (int v:adj[u][t])
{
p[v][0][t]=u;
dfs(v,t);
}
tout[u][t]=tour;
}
void fenwick_update(int u,int v)
{
for (int idx=u;idx<=n;idx+=idx&-idx)
bit[idx]+=v;
}
int fenwick_get(int u)
{
int ans=0;
for (int idx=u;idx>0;idx-=idx&-idx)
ans+=bit[idx];
return ans;
}
void solve()
{
for (int i=0;i<m;i++)
{
X[i]++;
Y[i]++;
}
for (int i=0;i<request;i++)
{
S[i]++;
E[i]++;
L[i]++;
R[i]++;
}
for (int i=0;i<m;i++)
{
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
for (int i=1;i<=n;i++)
par[i][0]=par[i][1]=-1;
for (int i=1;i<=n;i++)
for (int j:g[i])
if (i>j) join(i,j,0);
for (int i=n;i>=1;i--)
for (int j:g[i])
if (i<j) join(i,j,1);
tour=0;
dfs(root[0],0);
tour=0;
dfs(root[1],1);
h=31-__builtin_clz(n);
for (int j=1;j<=h;j++)
for (int i=1;i<=n;i++)
{
p[i][j][0]=p[p[i][j-1][0]][j-1][0];
p[i][j][1]=p[p[i][j-1][1]][j-1][1];
}
for (int i=0;i<request;i++)
{
int l=L[i],r=R[i],s=S[i],e=E[i];
for (int j=h;j>=0;j--)
{
if (p[s][j][1]>=l) s=p[s][j][1];
if (p[e][j][0]<=r and p[e][j][0]!=0) e=p[e][j][0];
}
query[tout[e][0]].push_back(make_pair(i,1));
query[tin[e][0]-1].push_back(make_pair(i,-1));
L[i]=tin[s][1];
R[i]=tout[s][1];
}
for (int i=1;i<=n;i++)
{
fenwick_update(tin[arr[i][0]][1],1);
for (pii j:query[i])
ans[j.X]+=(fenwick_get(R[j.X])-fenwick_get(L[j.X]-1))*j.Y;
}
for (int i=0;i<request;i++)
ans[i]=(ans[i]>0);
}
}
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;
ans.resize(request);
sub4::solve();
return ans;
}
