#include <bits/stdc++.h>
#include "werewolf.h"
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef pair <ii,ii> iiii;
typedef vector <lli> vi;
typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int n,m,q,co1=0,co2=0;
vi al[2*100001],al1[5*100001],al2[5*100001];
vector<ii> qu1[2*100001],qu2[2*100001];
int r1[2*100001],r2[2*100001],par1[5*100001],par2[5*100001],preco1=0,preco2=0,pre1[2*100001],pre2[2*100001];
ii nr1[5*100001],nr2[5*100001];
int segt1[4*2*100001];
vector<ii> gr;
int find1(int f)
{
if(par1[par1[f]]!=par1[f]) par1[f]=find1(par1[f]);
return par1[f];
}
int find2(int f)
{
if(par2[par2[f]]!=par2[f]) par2[f]=find2(par2[f]);
return par2[f];
}
void add1(int v)
{
al[v].pb(v);
par1[co1]=co1;
for(int i=0;i<al[v].size();++i)
{
if(al[v][i]>=v)
{
int p=find1(al[v][i]);
if(p==co1)
continue;
al1[co1].pb(p);
par1[p]=co1;
}
}
co1++;
}
void answer1(int v)
{
for(int j=0;j<qu1[v].size();++j)
r1[qu1[v][j].S]=find1(qu1[v][j].F);
}
void add2(int v)
{
par2[co2]=co2;
al[v].pb(v);
for(int i=0;i<al[v].size();++i)
{
if(al[v][i]<=v)
{
int p=find2(al[v][i]);
if(p==co2)
continue;
al2[co2].pb(p);
par2[p]=co2;
}
}
co2++;
}
void answer2(int v)
{
for(int j=0;j<qu2[v].size();++j)
r2[qu2[v][j].S]=find2(qu2[v][j].F);
}
void dfs1(int node)
{
if(al1[node].size()==0)
{
pre1[node]=preco1;
nr1[node]=mp(preco1,preco1);
preco1++;
}
else
nr1[node]=mp(n+10,-1);
for(int i=0;i<al1[node].size();++i)
{
dfs1(al1[node][i]);
nr1[node].F=min(nr1[node].F,nr1[al1[node][i]].F);
nr1[node].S=max(nr1[node].S,nr1[al1[node][i]].S);
}
}
void dfs2(int node)
{
if(al2[node].size()==0)
{
pre2[node]=preco2;
nr2[node]=mp(preco2,preco2);
preco2++;
}
else
nr2[node]=mp(n+20,-2);
for(int i=0;i<al2[node].size();++i)
{
dfs2(al2[node][i]);
nr2[node].F=min(nr2[node].F,nr2[al2[node][i]].F);
nr2[node].S=max(nr2[node].S,nr2[al2[node][i]].S);
}
}
void up1(int node,int l,int r,int in)
{
if(l==r)
{
segt1[node]+=1;
return;
}
int mid=(l+r)/2;
if(in<=mid)
up1(2*node+1,l,mid,in);
else
up1(2*node+2,mid+1,r,in);
segt1[node]=segt1[2*node+1]+segt1[2*node+2];
}
int query1(int node,int l,int r,int s,int e)
{
if(l>e||r<s)
return 0;
if(l>=s&&r<=e)
return segt1[node];
int mid=(l+r)/2;
int q1=query1(2*node+1,l,mid,s,e);
int q2=query1(2*node+2,mid+1,r,s,e);
return q1+q2;
}
vector<iiii> rqu1[2*100001];
int ans[5*100001];
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;
q=S.size();
m=X.size();
for(int i=0;i<n;++i)
{
par1[i]=i;
par2[i]=i;
}
co1=n;
co2=n;
for(int i=0;i<m;++i)
{
al[X[i]].pb(Y[i]);
al[Y[i]].pb(X[i]);
}
for(int i=0;i<q;++i)
{
qu1[L[i]].pb(mp(S[i],i));
qu2[R[i]].pb(mp(E[i],i));
}
for(int i=n-1;i>=0;--i)
{
add1(i);
answer1(i);
}
for(int i=0;i<n;++i)
{
add2(i);
answer2(i);
}
dfs1(co1-1);
dfs2(co2-1);
for(int i=0;i<n;++i)
gr.pb(mp(pre1[i],pre2[i]));
sort(all(gr));
for(int i=0;i<q;++i)
{
int x1=nr1[r1[i]].F,x2=nr1[r1[i]].S,y1=nr2[r2[i]].F,y2=nr2[r2[i]].S;
if(x1-1>=0)
rqu1[x1-1].pb(mp(mp(y1,y2),mp(i,1)));
rqu1[x2].pb(mp(mp(y1,y2),mp(i,2)));
}
for(int i=0;i<n;++i)
{
up1(0,0,n-1,gr[i].S);
while(rqu1[i].size())
{
if(rqu1[i].back().S.S==1)
ans[rqu1[i].back().S.F]+=-query1(0,0,n-1,rqu1[i].back().F.F,rqu1[i].back().F.S);
else
ans[rqu1[i].back().S.F]+=+query1(0,0,n-1,rqu1[i].back().F.F,rqu1[i].back().F.S);
rqu1[i].pop_back();
}
}
vector<int> A;
for(int i=0;i<q;++i)
{
if(ans[i]>0)
A.pb(1);
else
A.pb(0);
}
return A;
}
