#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>order;
void dfs(int st, vector<int>g[], bool vis[]){
vis[st]=1;
order.push_back(st);
for(int i : g[st]){
if(vis[i])
continue;
dfs(i,g,vis);
}
}
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();
vector<int>g[n];
int m = x.size();
for(int i = 0;i<m;i++){
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
order.clear();
bool vis[n];
fill(vis,vis+n,0);
for(int i = 0;i<n;i++){
if(g[i].size()==1){
dfs(i,g,vis);
break;
}
}
//order acquired;
assert(order.size()==n);
vector<int>pos(n);
for(int i = 0;i<n;i++){
pos[order[i]]=i;
}
set<int>inds;
int lefh[n][20];
int righ[n][20];
for(int i = 0;i<n;i++){
fill(lefh[i],lefh[i]+20,i);
fill(righ[i],righ[i]+20,i);
}
for(int i = 0;i<n;i++){
int ind = pos[i];
//i is at ind index.
int rig = ind;
auto it = inds.lower_bound(ind);
if(it!=inds.end()){
rig=*it;
}
int lef = ind;
if(it!=inds.begin()){
it--;
lef=*it;
}
lefh[ind][0]=lef;
righ[ind][0]=rig;
for(int j = 1;j<20;j++){
lefh[ind][j]=lefh[lefh[ind][j-1]][j-1];
righ[ind][j]=righ[righ[ind][j-1]][j-1];
}
inds.insert(ind);
}
//all index of node whose val is strictly less than val of node at current index is stored in lefh, similar in righ
inds.clear();
int lefw[n][20];
int rigw[n][20];
for(int i = 0;i<n;i++){
fill(lefw[i],lefw[i]+20,i);
fill(rigw[i],rigw[i]+20,i);
}
for(int i = n-1;i>=0;i--){
int ind = pos[i];
//i is at ind index.
int rig = ind;
auto it = inds.lower_bound(ind);
if(it!=inds.end()){
rig=*it;
}
int lef = ind;
if(it!=inds.begin()){
it--;
lef=*it;
}
lefw[ind][0]=lef;
rigw[ind][0]=rig;
for(int j = 1;j<20;j++){
lefw[ind][j]=lefw[lefw[ind][j-1]][j-1];
rigw[ind][j]=rigw[rigw[ind][j-1]][j-1];
}
inds.insert(ind);
}
vector<int>ans(q);
for(int i = 0;i<q;i++){
int limh = pos[s[i]];
for(int j = 19;j>=0;j--){
if(order[lefh[limh][j]]<l[i])
continue;
limh=lefh[limh][j];
}
for(int j = 19;j>=0;j--){
if(order[righ[limh][j]]<l[i])
continue;
limh=righ[limh][j];
}
int limw = pos[e[i]];
for(int j = 19;j>=0;j--){
if(order[lefw[limw][j]]>r[i])
continue;
limw=lefw[limw][j];
}
for(int j = 19;j>=0;j--){
if(order[rigw[limw][j]]>r[i])
continue;
limw=rigw[limw][j];
}
int l1 = lefh[limh][0]+(lefh[limh][0]!=limh);
int r1 = righ[limh][0]-(righ[limh][0]!=limh);
int l2 = lefw[limw][0]+(lefw[limw][0]!=limw);
int r2 = rigw[limw][0]-(rigw[limw][0]!=limw);
assert(l1<=r1);
assert(l2<=r2);
if(l1>r2||r1<l2){
ans[i]=0;
}
else{
ans[i]=1;
}
}
return ans;
}
