#include "werewolf.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
using namespace std;
using pii=pair <int,int>;
int dsu[400040];
void init(int sz){
for (int i=0; i<sz; i++) dsu[i]=i;
}
int prt(int node){
if (dsu[node]==node) return node;
return dsu[node]=prt(dsu[node]);
}
void unn(int u,int v){
u=prt(u); v=prt(v);
if (u==v) return;
dsu[u]=dsu[v];
}
bool cmp1(pii a,pii b){
return min(a.x,a.y)>min(b.x,b.y);
}
bool cmp2(pii a,pii b){
return max(a.x,a.y)<max(b.x,b.y);
}
vector <int> humanGraph[400040],wolfGraph[400040];
int humanP[400040],wolfP[400040]; //leaves permutation
pii humanR[400040],wolfR[400040]; //range
int tme;
int humanval[400040],wolfval[400040];
int humanlca[400040][19],wolflca[400040][19];
pii humanDfs(int cur,int prv){
humanlca[cur][0]=prv;
if (humanGraph[cur].empty()){
humanP[tme]=cur;
tme++;
return humanR[cur]={tme-1,tme-1};
}
vector <pii> ranges;
for (auto i:humanGraph[cur]) ranges.pb(humanDfs(i,cur));
sort(ranges.begin(),ranges.end());
return humanR[cur]={ranges.front().x,ranges.back().y};
}
pii wolfDfs(int cur,int prv){
wolflca[cur][0]=prv;
if (wolfGraph[cur].empty()){
wolfP[tme]=cur;
tme++;
return wolfR[cur]={tme-1,tme-1};
}
vector <pii> ranges;
for (auto i:wolfGraph[cur]) ranges.pb(wolfDfs(i,cur));
sort(ranges.begin(),ranges.end());
return wolfR[cur]={ranges.front().x,ranges.back().y};
}
struct wavelet{
int lo,hi;
wavelet *lhs=0,*rhs=0;
vector <int> b;
wavelet(vector<int>v):wavelet(v.begin(),v.end(),*min_element(v.begin(),v.end()),*max_element(v.begin(),v.end())){};
~wavelet(){
if (lhs) delete lhs;
if (rhs) delete rhs;
}
template <typename T> wavelet(T from,T to,int lo_,int hi_){
lo=lo_;
hi=hi_;
if (from>=to||lo==hi) return;
int mi=lo+(hi-lo)/2;
auto f=[&](int r){
return r<=mi;
};
b.reserve(to-from+1);
b.push_back(0);
for (auto it=from; it!=to; it++) b.push_back(b.back()+f(*it));
auto mit=stable_partition(from,to,f);
lhs=new wavelet(from,mit,lo,mi);
rhs=new wavelet(mit,to,mi+1,hi);
}
int lte(int l,int r,int k){
if (l>r||k<lo) return 0;
if (hi<=k) return r-l+1;
return this->lhs->lte(b[l],b[r+1]-1,k)+this->rhs->lte(l-b[l],r-b[r+1],k);
}
};
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 m=X.size();
vector <pii> edge;
for (int i=0; i<m; i++) edge.pb({X[i],Y[i]});
sort(edge.begin(),edge.end(),cmp1);
init(2*N);
int cur=N;
for (int i=0; i<N; i++) humanval[i]=i;
for (auto i:edge){
if (prt(i.x)==prt(i.y)) continue;
humanGraph[cur].pb(prt(i.x));
humanGraph[cur].pb(prt(i.y));
humanval[cur]=min(humanval[prt(i.x)],humanval[prt(i.y)]);
unn(i.x,cur);
unn(i.y,cur);
cur++;
}
tme=0;
for (int i=0; i<2*N; i++){
for (int j=0; j<19; j++) humanlca[i][j]=-1;
}
humanDfs(cur-1,-1);
for (int j=1; j<19; j++){
for (int i=0; i<2*N; i++){
if (humanlca[i][j-1]==-1) humanlca[i][j]=-1;
else humanlca[i][j]=humanlca[humanlca[i][j-1]][j-1];
}
}
sort(edge.begin(),edge.end(),cmp2);
init(2*N);
cur=N;
for (int i=0; i<N; i++) wolfval[i]=i;
for (int i=N; i<2*N; i++) wolfval[i]=1e9;
for (auto i:edge){
if (prt(i.x)==prt(i.y)) continue;
wolfGraph[cur].pb(prt(i.x));
wolfGraph[cur].pb(prt(i.y));
wolfval[cur]=max(wolfval[prt(i.x)],wolfval[prt(i.y)]);
unn(i.x,cur);
unn(i.y,cur);
cur++;
}
tme=0;
for (int i=0; i<2*N; i++){
for (int j=0; j<19; j++) wolflca[i][j]=-1;
}
wolfDfs(cur-1,-1);
for (int j=1; j<19; j++){
for (int i=0; i<2*N; i++){
if (wolflca[i][j-1]==-1) wolflca[i][j]=-1;
else wolflca[i][j]=wolflca[wolflca[i][j-1]][j-1];
}
}
vector <int> poshuman(N);
for (int i=0; i<N; i++) poshuman[humanP[i]]=i;
vector <int> r(N);
for (int i=0; i<N; i++) r[i]=poshuman[wolfP[i]];
wavelet tree(r);
vector <int> ans;
for (int Q=0; Q<S.size(); Q++){
int st=S[Q],en=E[Q];
if (humanval[st]<L[Q]||wolfval[en]>R[Q]){
ans.pb(-1);
continue;
}
for (int i=18; i>=0; i--){
if (humanlca[st][i]==-1) continue;
if (humanval[humanlca[st][i]]>=L[Q]) st=humanlca[st][i];
}
for (int i=18; i>=0; i--){
if (wolflca[en][i]==-1) continue;
if (wolfval[wolflca[en][i]]<=R[Q]) en=wolflca[en][i];
}
if (tree.lte(wolfR[en].x,wolfR[en].y,humanR[st].y)!=tree.lte(wolfR[en].x,wolfR[en].y,humanR[st].x-1)) ans.pb(1);
else ans.pb(0);
}
return ans;
}
/*
signed main(){
int N,M,Q;
cin>>N>>M>>Q;
vector <int> X,Y,S,E,L,R;
for (int i=0; i<M; i++){
int xj,yj;
cin>>xj>>yj;
X.pb(xj);
Y.pb(yj);
}
for (int i=0; i<Q; i++){
int si,ei,li,ri;
cin>>si>>ei>>li>>ri;
S.push_back(si);
E.push_back(ei);
L.push_back(li);
R.push_back(ri);
}
vector <int> ans=check_validity(N,X,Y,S,E,L,R);
for (int i:ans) cout<<i<<' ';
}
*/
