#include"werewolf.h"
#include<queue>
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
int n,m,q;
vector<int>nodes[200000];
vector<bool>reachable2(int s,int t){
vector<bool>vis(n);
queue<int>q;
q.push(s);
while(q.size()){
int node=q.front();
q.pop();
if(vis[node]||node<t)
continue;
vis[node]=true;
for(int ne:nodes[node])
q.push(ne);
}
return vis;
}
struct Query{
int S,E,L,R;
int ans;
};
bool cmp(Query*a,Query*b){
return a->L>b->L;
}
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R){
n=N;
m=(int)X.size();
q=(int)S.size();
for(int i=0;i<n;i++){
nodes[i].clear();
}
for(int i=0;i<m;i++){
nodes[X[i]].push_back(Y[i]);
nodes[Y[i]].push_back(X[i]);
}
vector<int>line;
{
vector<int>comp(n);
vector<vector<int>>comps(n);
for(int i=0;i<n;i++){
comps[i]={i};
set<int>to_add;
for(int ne:nodes[i]){
if(ne>i)
continue;
to_add.insert(comp[ne]);
}
for(int j:to_add){
comps[i].insert(comps[i].end(),comps[j].begin(),comps[j].end());
comps[i].push_back(i);
}
for(int j:comps[i])
comp[j]=i;
}
line=comps[comp[0]];
}
/*for(int i:line)
cout<<i<<" ";
cout<<"\n";*/
vector<Query*>qrs(q);
for(int i=0;i<q;i++){
qrs[i]=new Query;
qrs[i]->S=S[i];
qrs[i]->E=E[i];
qrs[i]->L=L[i];
qrs[i]->R=R[i];
qrs[i]->ans=0;
}
vector<Query*>srt=qrs;
sort(srt.begin(),srt.end(),cmp);
vector<int>comp(n);
vector<vector<int>>comps(n);
int r=n-1;
for(auto qry:srt){
while(r>=qry->L){
comp[r]=r;
comps[r]={r};
for(int ne:nodes[r]){
if(ne<r)
continue;
if(comp[ne]!=comp[r]){
comps[comp[r]].insert(comps[comp[r]].end(),comps[comp[ne]].begin(),comps[comp[ne]].end());
for(int i:comps[comp[r]])
comp[i]=comp[r];
}
}
r--;
}
//vector<bool>v1=reachable2(qry->S,qry->L);
vector<bool>v1(n);
for(int i:comps[comp[qry->S]])
v1[i]=true;
vector<bool>v2(n);
for(int j=0;j<(int)line.size();j++){
if(line[j]==qry->E){
for(int k=j;k<(int)line.size()&&line[k]<=qry->R;k++)
v2[line[k]]=true;
for(int k=j;k>=0&&line[k]<=qry->R;k--)
v2[line[k]]=true;
break;
}
}
for(int j=0;j<n;j++)
if(v1[j]&&v2[j])
qry->ans=1;
}
vector<int>res(q);
for(int i=0;i<q;i++)
res[i]=qrs[i]->ans;
return res;
}
