#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
long long n,m,dsu[200069],pst[200069],sbt[200069],pr[200069][18],cc[200069];
vector<long long> al[200069],al2[200069];
pair<pair<long long,long long>,long long> qq[200069];
pair<long long,long long> qs[200069];
multiset<long long> ms[200069];
bitset<200069> sq;
long long fd(long long x)
{
if(dsu[x]!=x)
{
dsu[x]=fd(dsu[x]);
}
return dsu[x];
}
void bd(long long x)
{
long long i,j,sz=al2[x].size(),l;
n++;
pst[x]=n;
sbt[x]=1;
for(i=0;i<sz;i++)
{
l=al2[x][i];
pr[l][0]=x;
for(j=1;j<18;j++)
{
pr[l][j]=pr[pr[l][j-1]][j-1];
}
bd(l);
sbt[x]+=sbt[l];
}
}
void jo(long long x,long long y)
{
multiset<long long>::iterator it;
x=fd(x);
y=fd(y);
if(cc[x]<cc[y])
{
swap(x,y);
}
for(it=ms[y].begin();it!=ms[y].end();it++)
{
ms[x].insert(*it);
}
cc[x]+=cc[y];
dsu[y]=x;
}
vector<int> check_validity(int on,vector<int> ka,vector<int> la,vector<int> sta,vector<int> fna,vector<int> lba,vector<int> rba)
{
long long t=sta.size(),rr,i,j,k,l,w,sz,pz;
multiset<long long>::iterator it;
vector<int> v;
n=on;
m=ka.size();
for(i=0;i<m;i++)
{
k=ka[i]+1;
l=la[i]+1;
al[k].push_back(l);
al[l].push_back(k);
}
for(i=n;i;i--)
{
dsu[i]=i;
sz=al[i].size();
for(j=0;j<sz;j++)
{
l=al[i][j];
if(l>i&&fd(l)!=i)
{
al2[i].push_back(fd(l));
dsu[fd(l)]=i;
}
}
}
n=0;
bd(1);
for(rr=1;rr<=t;rr++)
{
qq[rr]={{sta[rr-1]+1,fna[rr-1]+1},lba[rr-1]+1};
qs[rr]={rba[rr-1]+1,rr};
}
sort(qs+1,qs+t+1);
for(i=0,rr=1;rr<=t;rr++)
{
k=qs[rr].fr;
pz=qs[rr].sc;
for(;i<k;)
{
i++;
dsu[i]=i;
cc[i]=1;
ms[i].insert(pst[i]);
sz=al[i].size();
for(j=0;j<sz;j++)
{
l=al[i][j];
if(l<i&&fd(l)!=fd(i))
{
jo(i,l);
}
}
}
k=qq[pz].fr.fr;
l=qq[pz].fr.sc;
w=qq[pz].sc;
for(j=17;j+1;j--)
{
if(pr[k][j]>=w)
{
k=pr[k][j];
}
}
it=ms[fd(l)].lower_bound(pst[k]);
sq[pz]=it!=ms[fd(l)].end()&&*it<=pst[k]+sbt[k]-1;
}
for(rr=1;rr<=t;rr++)
{
v.push_back(sq[rr]);
}
return v;
}
