#include "werewolf.h"
#include <cstdio>
#include <cstdlib>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int par[2][N],p[2][N][25],sz[2][N],tmin[2][N],tmout[2][N],timer,Lg,F,bbb,i;
vector<int>v[N],V[2][N],tree[4*N];
vector<pair<int,int> >e[2];
set<int> P[2][N];
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int find_parent(int u,int t){
if(par[t][u]==u) return u;
return par[t][u]=find_parent(par[t][u],t);
}
void merge(int u,int v,int t){
int p1=find_parent(u,t);
int p2=find_parent(v,t);
if(p1==p2) return;
if(!t)V[t][u].push_back(*P[t][p2].begin()),V[t][*P[t][p2].begin()].push_back(u);
else V[t][u].push_back(*--P[t][p2].end()),V[t][*--P[t][p2].end()].push_back(u),
e[1].push_back({u,*--P[t][p2].end()}),e[1].push_back({*--P[t][p2].end(),u});
if(P[t][p1].size()<P[t][p2].size()) swap(p1,p2);
while(P[t][p2].size()){
int cc=*P[t][p2].begin();
P[t][p1].insert(cc);
par[t][cc]=p1;
P[t][p2].erase(cc);
}
}
void dfs(int u,int t){
timer++;
tmin[t][u]=timer;
for(int j=1;j<Lg;j++){
p[t][u][j]=p[t][p[t][u][j-1]][j-1];
}
for(int i=0;i<V[t][u].size();i++){
if(p[t][u][0]==V[t][u][i]) continue;
if(!t && V[t][u][i]<u) cout<<1/bbb<<endl;
if(t && V[t][u][i]>u) cout<<1/bbb<<endl;
p[t][V[t][u][i]][0]=u;
dfs(V[t][u][i],t);
}
tmout[t][u]=timer;
}
void update(int u,int ind,int l,int r,int val){
if(l>ind || r<ind) return;
if(l==r) {
tree[u].push_back(val);
return;
}
tree[u].push_back(val);
if(tree[u].size()==r-l+1) sort(tree[u].begin(),tree[u].end());
int mid=(l+r)/2;
update(2*u,ind,l,mid,val);
update(2*u+1,ind,mid+1,r,val);
}
int getans(int u,int start,int end,int l,int r,int L,int R){
if(l>end || r<start) return 0;
if(l>=start && r<=end){
int ans=-1;
int le=0;int ri=tree[u].size()-1;
while(le<=ri){
int mid=(le+ri)/2;
if(tree[u][mid]<L){
ans=mid; le=mid+1;
}
else ri=mid-1;
}
int cnt=ans+1;
ans=tree[u].size();
le=0; ri=tree[u].size()-1;
while(le<=ri){
int mid=(le+ri)/2;
if(tree[u][mid]>R){
ans=mid; ri=mid-1;
}
else le=mid+1;
}
cnt+=tree[u].size()-ans;
return cnt;
}
int mid=(l+r)/2;
return getans(2*u,start,end,l,mid,L,R)+getans(2*u+1,start,end,mid+1,r,L,R);
}
int Lca(int u,int m,int t){
for(int i=Lg;i>=0;i--){
if(p[t][u][i] && ((!t && p[t][u][i]>=m)||(t && p[t][u][i]<=m))){
u=p[t][u][i];
}
}
return u;
}
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) {
int M = X.size();
Lg=log2(N)+1;
for(int i=1;i<=N;i++)
for(int j=0;j<=1;j++)
par[j][i]=i,P[j][i].insert(i);
for(int i=0;i<M;i++){
X[i]++; Y[i]++;
v[X[i]].push_back(Y[i]);
v[Y[i]].push_back(X[i]);
}
for(int i=N;i>=1;i--){
sort(v[i].begin(),v[i].end());
for(int j=0;j<v[i].size();j++){
int nxt=v[i][j];
if(nxt>i){
merge(i,nxt,0);
}
}
}
timer=0;
dfs(1,0);
for(int i=1;i<=N;i++){
reverse(v[i].begin(),v[i].end());
for(int j=0;j<v[i].size();j++){
int nxt=v[i][j];
if(nxt<i){
merge(i,nxt,1);
}
}
}
int Q=S.size();vector<int>Ans(Q);
timer=0;
dfs(N,1);
for(int i=1;i<=N;i++){
update(1,tmin[0][i],1,N,tmin[1][i]);
}
for(int i=0;i<Q;i++){
S[i]++;
E[i]++;
L[i]++;
R[i]++; F=i;
int x=Lca(S[i],L[i],0);
int y=Lca(E[i],R[i],1);
if(tmout[0][x]-tmin[0][x]+1-getans(1,tmin[0][x],tmout[0][x],1,N,tmin[1][y],tmout[1][y])) Ans[i]=1;
else Ans[i]=0;
}
return Ans;
}
