#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define M 200100
typedef vector<int> VI;
struct dsu{
int par[M];
int abp(int n){
return par[n]?par[n]=abp(par[n]):n;
}
int merge(int a,int b){
a++;b++;
a=abp(a),b=abp(b);
if(a-b)par[a]=b;
return a!=b;
}
} dsuhuman,dsuwolf;
int bjh[M][20],bjw[M][20],in[M],out[M],CC;
vector<pair<int,int>>qry[M];
set<int>st[M];
VI EDGES[M],adjh[M],adjw[M];
vector<int>ans;
void dfsw(int n){
in[n]=++CC;
for(auto i:adjw[n])
dfsw(i);
out[n]=CC;
}
void merge(int a,int b){
if(st[a].size()<st[b].size())
swap(st[a],st[b]);
for(auto i:st[b])
st[a].insert(i);
st[b].clear();
}
void dfsans(int n){
st[n].insert(in[n]);
for(auto i:adjh[n])
dfsans(i),merge(n,i);
for(auto[i,x]:qry[n])
ans[i]=st[n].lower_bound(in[x])!=
st[n].upper_bound(out[x]);
}
VI check_validity(int N,VI X,VI Y,VI S,VI E,VI L,VI R) {
for(int i=0;i<X.size();i++)
EDGES[X[i]].push_back(Y[i]),
EDGES[Y[i]].push_back(X[i]);
for(int i=N;i--;)
for(auto k:EDGES[i]) {
if(k<i)continue;
int x=dsuhuman.abp(k+1)-1;
if(x==i) continue;
bjh[x][0]=i,adjh[i].push_back(x);
dsuhuman.merge(x,i);
}
for(int i=0;i<N;i++)
for(auto k:EDGES[i]) {
if(k>i)continue;
int x=dsuwolf.abp(k+1)-1;
if(x==i) continue;
bjw[x][0]=i,adjw[i].push_back(x);
dsuwolf.merge(x,i);
}
bjw[N-1][0]=bjw[N][0]=N;
for(int j=1;j<20;j++)
for(int i=0;i<=N;i++)
bjw[i][j]=bjw[bjw[i][j-1]][j-1],
bjh[i][j]=bjh[bjh[i][j-1]][j-1];
dfsw(N-1);
int Q=S.size();
ans=S;
for(int i=0;i<Q;i++){
int l=L[i],r=R[i],s=S[i],e=E[i];
for(int i=20;i--;)
if(bjh[s][i]>=l)
s=bjh[s][i];
for(int i=20;i--;)
if(bjw[e][i]<=r)
e=bjw[e][i];
qry[s].push_back({i,e});
}
dfsans(0);
return ans;
}
