#include "werewolf.h"
#pragma GCC optimize("O3", "inline")
#define skillissue <bits/stdc++.h>
#define ultra_mal std
#include skillissue
using namespace ultra_mal;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ins insert
#define pb push_back
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define hash FhashF
const int mod = 1e9 +7, sze = 2e5 +300, inf = INT_MAX, P = 1453;
vector<int> graph[sze];
vector<int> arr,arr2;
int idx[sze],idx2[sze];
const int L = 20;
int lg[sze];
int dpmx[L][sze],dpmn[L][sze];
int dpmx2[L][sze],dpmn2[L][sze];
void dfs(int node,int par=-1){
idx[node]=arr.size();
arr.pb(node);
for(auto v:graph[node]){
if(v!=par){
dfs(v,node);
}
}
}
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();
for(int i=2;i<sze;i++){
lg[i]=lg[i/2]+1;
}
vector<int> A(Q);
int m = X.size();
for(int i=0;i<m;i++){
graph[X[i]].pb(Y[i]);
graph[Y[i]].pb(X[i]);
}
int x =0;
for(int i =0;i<n;i++){
if(graph[i].size()==1){
x=i;
break;
}
}
dfs(x);
arr2=arr;
int j= 0;
reverse(all(arr2));
for(auto v:arr2){
idx2[v]=j++;
}
j=0;// fobi
for(int i=0;i<n;i++){
dpmn[0][i]=arr[i];
dpmx[0][i]=arr[i];
dpmn2[0][i]=arr2[i];
dpmx2[0][i]=arr2[i];
}
for(int i=1;i<20;i++){
for(int j=0;j + (1<<i)<=n;j++){
dpmn[i][j]= min(dpmn[i-1][j],dpmn[i-1][j + (1<<(i-1))]);
dpmx[i][j]= max(dpmx[i-1][j],dpmx[i-1][j + (1<<(i-1))]);
dpmn2[i][j]= min(dpmn2[i-1][j],dpmn2[i-1][j + (1<<(i-1))]);
dpmx2[i][j]= max(dpmx2[i-1][j],dpmx2[i-1][j + (1<<(i-1))]);
}
}
auto qry = [&](int l,int r) -> pii {
int len =lg[r-l+1];
return { min(dpmn[len][l],dpmn[len][r - (1<<len)+1]),
max(dpmx[len][l],dpmx[len][r - (1<<len)+1])};
};
auto qry2 = [&](int l,int r) -> pii {
int len =lg[r-l+1];
return { min(dpmn2[len][l],dpmn2[len][r - (1<<len)+1]),
max(dpmx2[len][l],dpmx2[len][r - (1<<len)+1])};
};
for(int i=0;i<Q;i++){
A[i]=0;
int start = S[i];
int finish = E[i];
int wl = L[i];
int wr = R[i];
int l,r,ans = -1;
if(idx[start]<idx[finish]){
l = idx[start];
r = idx[finish];
while(l<=r){
int mid = (l+r)/2;
pii res = qry(idx[start],mid);
if(res.second <= wr){
l=mid+1;
ans=max(ans,mid);
}
else{
r=mid-1;
}
}
if(ans!=-1 && qry(ans,idx[finish]).first>=wl && arr[ans]>=wl && arr[ans]<=wr){
A[i]=1;
}
}
else{ // reverse
l = idx2[start];
r = idx2[finish];
while(l<=r){
int mid = (l+r)/2;
pii res = qry2(idx2[start],mid);
if(res.second <= wr){
l=mid+1;
ans=max(ans,mid);
}
else{
r=mid-1;
}
}
if(ans!=-1 && qry2(ans,idx2[finish]).first>=wl && arr2[ans]>=wl && arr2[ans]<=wr){
A[i]=1;
}
}
}
return A;
}
