#include<iostream>
#include<vector>
#include<tuple>
#include "werewolf.h"
using namespace std;
const int MAX_N=2e5+5;
const int MAX_M=4e5+5;
const int BLOCK_SIZE=5000;
int n,m,q;
vector<int>g[MAX_N];
int l[MAX_N];
int r[MAX_N];
int s[MAX_N];
int e[MAX_N];
vector<int>forleft[MAX_N],forright[MAX_N];
vector<pair<int,int>>checkone[MAX_N];
int pare[MAX_N];
///init
vector<pair<int,int>>updates[MAX_N];
int prevblockcnt[MAX_N];
vector<int>blockqueries[MAX_N];
///blocks
int parent[MAX_N],sz[MAX_N];
int curtime;
int Find(int u)
{
if(parent[u]==u)return u;
return parent[u]=Find(parent[u]);
}
void Merge(int u,int v,bool f)
{
int urt=Find(u),vrt=Find(v);
if(urt==vrt)return;
if(sz[urt]>sz[vrt])swap(urt,vrt);
parent[urt]=vrt;
sz[vrt]+=sz[urt];
if(!f)return;
for(auto [node,useless]:updates[urt])
{
updates[vrt].push_back({node,curtime});
}
}
///dsu
void Update(int query)
{
int node=pare[query];
int posr,br;
int ll=0,rr=updates[node].size()-1;
while(ll<=rr)
{
int mid=(ll+rr)/2;
if(updates[node][mid].second<=r[query])
{
posr=mid;
ll=mid+1;
}
else rr=mid-1;
}
br=posr/BLOCK_SIZE;
for(int b=0;b<br;b++)
{
blockqueries[prevblockcnt[node]+b+1].push_back(query);
}
for(int i=br*BLOCK_SIZE;i<=posr;i++)
{
checkone[l[query]].push_back({updates[node][i].first,query});
}
}
vector<int>nodes;
vector<int>ans;
bool active[MAX_N];
bool used[MAX_N];
void dfs(int u)
{
used[u]=1;
for(int v:g[u])
{
if(v>=curtime && !used[v])dfs(v);
}
}
void bfs(int block)
{
int idxqueries=0;
for(int i=0;i<n;i++)used[i]=0;
for(int i=n-1;i>=0;i--)
{
if(active[i])used[i]=1;
for(int v:g[i])
{
if(v>i)
{
if(used[v]==used[i])continue;
curtime=i;
if(used[i])dfs(v);
else dfs(i);
}
}
while(idxqueries<blockqueries[block].size() && i==l[blockqueries[block][idxqueries]])
{
if(used[s[blockqueries[block][idxqueries]]])
{
ans[blockqueries[block][idxqueries]]=1;
}
idxqueries++;
}
}
for(int u:nodes)active[u]=0;
nodes.clear();
}
void solve()
{
for(int i=0;i<n;i++)
{
parent[i]=i;
sz[i]=i;
}
updates[0].push_back({0,0});
for(int i=1;i<n;i++)
{
curtime=i;
updates[i].push_back({i,i});
for(int v:g[i])
{
if(v<i)
{
Merge(v,i,1);
}
}
for(int query:forright[i])
{
pare[query]=Find(e[query]);
}
}
int curblockcnt=0;
for(int i=0;i<=n;i++)
{
prevblockcnt[i]=curblockcnt;
curblockcnt+=updates[i].size()/BLOCK_SIZE;
}
for(int i=n-1;i>=0;i--)
{
for(int query:forleft[i])Update(query);
}
///make queries
int block=1;
for(int i=0;i<n;i++)
{
int posl=0,posr=BLOCK_SIZE-1;
while(posr<updates[i].size())
{
if(blockqueries[block].size()>0)
{
for(int j=posl;j<=posr;j++)
{
nodes.push_back(updates[i][j].first);
active[updates[i][j].first]=1;
}
bfs(block);
}
block++;
posl+=BLOCK_SIZE;
posr+=BLOCK_SIZE;
}
}
//block queries
for(int i=0;i<n;i++)
{
parent[i]=i;
sz[i]=i;
}
for(int i=n-1;i>=0;i--)
{
for(int v:g[i])
{
if(v>i)
{
Merge(v,i,0);
}
}
for(auto [u,query]:checkone[i])
{
if(Find(u)==Find(s[query]))ans[query]=1;
}
}
//single node queries
///solve queries
}
std::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)
{
n=N;
m=X.size();
for(int i=0;i<m;i++)
{
int u=X[i],v=Y[i];
g[u].push_back(v);
g[v].push_back(u);
}
q=S.size();
ans.resize(q);
for(int i=0;i<q;i++)
{
s[i]=S[i];e[i]=E[i];l[i]=L[i];r[i]=R[i];
forleft[L[i]].push_back(i);
forright[R[i]].push_back(i);
}
solve();
return ans;
}
