#include "werewolf.h"
#include <bits/stdc++.h>
#define MAX 1000000000
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
int l,r;
bitset<200010> vh,vw;
vector<vi> G;
void dfs_human(int u){
if(u<l) return;
vh[u]=1;
for(auto &v:G[u]){
if(!vh[v]){
dfs_human(v);
}
}
}
void dfs_wolf(int u){
if(u>r) return;
vw[u]=1;
for(auto &v:G[u]){
if(!vw[v]){
dfs_wolf(v);
}
}
}
map<int,int> m;
vector<int> path;
int vis[200010];
ii tree[800010];
void dfs(int u){
path.push_back(u);
vis[u]=1;
for(auto &v: G[u]){
if(!vis[v]){
dfs(v);
}
}
}
void init(int node,int a,int b){
if(a>b) return;
if(a==b){
tree[node]=ii(path[a],path[a]);
return;
}
int mid=(a+b)/2;
init(2*node+1,a,mid);
init(2*node+2,mid+1,b);
tree[node].first=min(tree[2*node+1].first,tree[2*node+2].first);
tree[node].second=max(tree[2*node+1].second,tree[2*node+2].second);
}
int la,ra,lb,rb;
set<ii> si;
void query_hu(int node,int a,int b,int x){
if(a>b) return;
if(tree[node].first>=x){
si.insert(ii(a,b));
return;
}
if(a==b) return;
int mid=(a+b)/2;
query_hu(2*node+1,a,mid,x);
query_hu(2*node+2,mid+1,b,x);
}
void query_wolf(int node,int a,int b,int x){
if(a>b) return;
if(tree[node].second<=x){
si.insert(ii(a,b));
return;
}
if(a==b) return;
int mid=(a+b)/2;
query_wolf(2*node+1,a,mid,x);
query_wolf(2*node+2,mid+1,b,x);
}
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) {
G.resize(N+1);
for(int i=0;i<X.size();i++){
int u=X[i],v=Y[i];
G[u].push_back(v);
G[v].push_back(u);
}
bool sw=0;
int id;
for(int i=0;i<N;i++){
if(G[i].size()>2){
sw=1;
}
if(G[i].size()==1) id=i;
}
vector<int> res;
/* if(sw==1){
for(int i=0;i<S.size();i++){
l=L[i];
r=R[i];
vh.reset();
vw.reset();
dfs_human(S[i]);
dfs_wolf(E[i]);
bool sw=0;
for(int i=0;i<N;i++){
if(vh[i]==1 and vw[i]==1){
sw=1;
break;
}
}
res.push_back(sw);
}
}*/
// else{
dfs(id);
for(int i=0;i<path.size();i++){
m[path[i]]=i;
}
init(0,0,N-1);
int q=S.size();
for(int i=0;i<q;i++){
la=lb=MAX;
ra=rb=-MAX;
sw=0;
si.clear();
query_hu(0,0,N-1,L[i]);
set<ii>::iterator it=lower_bound(si.begin(),si.end(),ii(m[S[i]],0));
if(it==si.end()){
la=MAX;
ra=-MAX;
}
else{
if((*it).first>m[S[i]]) it--;
la=(*it).first;
ra=(*it).second;
}
set<ii>::iterator it1=it;
while(true){
it1++;
if(it1==si.end()) break;
if((*it1).first==ra+1){ra=(*it1).first;}
else{break;}
}
bool sw2=0;
while(true){
it--;
if((*it).second==la-1){la=(*it).second; }
else break;
if(it==si.begin()) break;
}
si.clear();
query_wolf(0,0,N-1,R[i]);
it=lower_bound(si.begin(),si.end(),ii(m[E[i]],0));
if(it==si.end()){
it--;
}
if((*it).first>m[E[i]]) it--;
lb=(*it).first;
rb=(*it).second;
it1=it;
while(true){
it1++;
if(it1==si.end()) break;
if((*it1).first==rb+1){rb=(*it1).first;}
else break;
}
sw2=0;
while(true){
it--;
if((*it).second==lb-1) lb=(*it).second;
else break;
if(it==si.begin()) break;
}
if(((la<=lb and ra>=lb) or (la<=rb and ra>=rb)) and la!=MAX and ra!=-MAX and lb!=MAX and rb!=-MAX){
res.push_back(1);
}
else{
res.push_back(0);
}
}
// }
return res;
}
