#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
using pii=pair<int,int>;
const int lim=2e5+100;
int n,m,q;
struct DSU{
int*parent;
DSU(){
parent=new int[n];
for(int i=0;i<n;i++){
parent[i]=i;
}
}
int find(int i){
if(i==parent[i])return i;
return parent[i]=find(parent[i]);
}
int unite(int i,int j){
i=find(i),j=find(j);
if(i==j)return 0;
parent[j]=i;
return 1;
}
};
struct ST{
int n,*tree;
ST(int n):n(n),tree(new int[2*n+10]){
for(int i=0;i<2*n+10;i++){
tree[i]=-1;
}
}
int query(int l,int r){
int ans=-1;
for(l+=n,r+=n+1;l<r;l>>=1,r>>=1){
if(l&1){
ans=max(ans,tree[l]);
l++;
}
if(r&1){
r--;
ans=max(ans,tree[r]);
}
}
return ans;
}
void update(int p,int val){
p+=n;
tree[p]=val;
// cerr<<p<<'\n';
for(p>>=1;p;p>>=1)tree[p]=max(tree[p<<1],tree[p<<1|1]);
}
};
vector<int>v[lim];
vector<int>tree[lim];
int jump[20][lim];
vector<int>tour;
vector<int>tin,tout;
void dfs(int node){
tin[node]=tour.size();
tour.pb(node);
for(int j:tree[node]){
// cerr<<node<<" --> "<<j<<'\n';
dfs(j);
}
tout[node]=tour.size()-1;
}
// state = 0 --> wolf ---- root = n-1
// state = 1 --> human ---- root = 0
array<vector<int>,3>calc(vector<int>bounds,vector<int>guys,int state){
for(int i=0;i<lim;i++)tree[i].clear();
for(int i=0;i<20;i++)for(int j=0;j<n;j++)jump[i][j]=-1;
tour.clear();
tin=tout=vector<int>(n);
// cerr<<"ok\n";
DSU dsu;
for(int i=state?n-1:0;state?0<=i:i<n;i+=state?-1:1){
if(state)sort(v[i].begin(),v[i].end());
else sort(v[i].begin(),v[i].end(),greater<int>());
for(int j:v[i]){
int x=dsu.find(i),y=dsu.find(j);
if((state^(j<i))&&dsu.unite(i,j)){
tree[x].pb(y);
jump[0][y]=x;
}
}
}
// cerr<<"ok\n";
for(int i=1;i<20;i++){
for(int j=0;j<n;j++){
jump[i][j]=jump[i-1][j]==-1?-1:jump[i-1][jump[i-1][j]];
}
}
// cerr<<"okk\n";
dfs(state?0:n-1);
// cerr<<"na bro\n";
vector<int>l,r;
for(int i=0;i<q;i++){
int bd=bounds[i],guy=guys[i];
// cerr<<"doing "<<guy<<' '<<bd<<'\n';
for(int j=19;0<=j;j--){
// cerr<<"try "<<jump[j][guy]<<'\n';
if(jump[j][guy]!=-1&&(state?bd<=jump[j][guy]:jump[j][guy]<=bd)){
guy=jump[j][guy];
// cerr<<"yep\n";
}//else cerr<<"nope\n";
}
// cerr<<guy<<'\n';
// cerr<<tin[guy]<<' '<<tout[guy]<<'\n';
l.pb(tin[guy]);
r.pb(tout[guy]);
}
// cerr<<"we gud\n";
// for(int i:l)cerr<<i<<' ';
// cerr<<'\n';
// for(int i:r)cerr<<i<<' ';
// cerr<<'\n';
return {tour,l,r};
}
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=X.size();
q=S.size();
for(int i=0;i<m;i++){
v[X[i]].pb(Y[i]);
v[Y[i]].pb(X[i]);
}
auto[wt,wl,wr]=calc(R,E,0);
auto[ht,hl,hr]=calc(L,S,1);
int tr[n];
for(int i=0;i<n;i++){
tr[ht[i]]=i;
// cerr<<ht[i]<<' '<<i<<'\n';
}
vector<int>beg[n];
for(int i=0;i<q;i++){
beg[wr[i]].pb(i);
}
vector<int>ans(q);
ST st(n);
// cerr<<"begin\n";
for(int i=0;i<n;i++){
// cerr<<"here\n";
// cerr<<i<<' '<<wt[i]<<' '<<tr[wt[i]]<<'\n';
// cerr<<"adding "<<i<<' '<<wt[i]<<' '<<tr[wt[i]]<<'\n';
st.update(tr[wt[i]],i);
// cerr<<"whaa\n";
for(int id:beg[i]){
// cerr<<id<<" :: "<<hl[id]<<' '<<hr[id]<<' '<<wl[id]<<' '<<wr[id]<<'\n';
int mx=st.query(hl[id],hr[id]);
// cerr<<"res :: "<<mx<<'\n';
ans[id]=mx>=wl[id];
}
}
return ans;
}
