#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
int const MAX=4e5+5;
vector<int>sons[MAX];
set<int>nodes[MAX];
int n;
vector<int>qL[MAX],qR[MAX];
vector<int>G[MAX];
int nod_inter[MAX];
int st[MAX],dr[MAX];
struct DSU{
int tata[MAX];
int id;
void init(){
int i;
for(i=0;i<n;++i)
tata[i]=0;
id=n-1;
}
int root(int nod){
if(!tata[nod])
return nod;
return tata[nod]=root(tata[nod]);
}
void uneste1(int u,int v){
u=root(u);
v=root(v);
if(u!=v){
++id;
sons[id].push_back(u);
sons[id].push_back(v);
tata[u]=id;
tata[v]=id;
}
}
void uneste2(int u,int v){
u=root(u);
v=root(v);
if(u!=v){
if(nodes[u].size()<nodes[v].size())
swap(u,v);
tata[v]=u;
nodes[u].insert(nodes[v].begin(),nodes[v].end());
nodes[v].clear();
}
}
}dsu;
void dfs(int nod){
static int time=0;
st[nod]=time;
for(auto fiu : sons[nod])
dfs(fiu);
if(sons[nod].empty())
++time;
dr[nod]=time-1;
}
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R) {
int q = S.size();
int m=X.size();
n=N;
int i;
for(i=0;i<q;++i){
qL[L[i]].push_back(i);
qR[R[i]].push_back(i);
}
for(i=0;i<m;++i){
G[X[i]].push_back(Y[i]);
G[Y[i]].push_back(X[i]);
}
dsu.init();
for(i=n-1;i>=0;--i){
for(auto vec : G[i])
if(vec>i)
dsu.uneste1(i,vec);
for(auto qry : qL[i])
nod_inter[qry]=dsu.root(S[qry]);
}
dfs(dsu.id);
dsu.init();
for(i=0;i<n;++i)
nodes[i].insert(st[i]);
vector<int>ans(q);
for(i=0;i<n;++i){
for(auto vec : G[i])
if(vec<i)
dsu.uneste2(vec,i);
for(auto qry : qR[i]){
int pos=E[qry];
int rt=dsu.root(pos);
int intv=nod_inter[qry];
auto it=nodes[rt].lower_bound(st[intv]);
if(it!=nodes[rt].end() && *it<=dr[intv])
ans[qry]=1;
else
ans[qry]=0;
}
}
return ans;
}
