#include "werewolf.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
using namespace std;
const int NN=2e6;
int par[22][NN],parr[NN],parrr[NN],n,m,q,t,b[NN],a[NN],sz[NN];
set<int> comp[NN];
vector<int> adj[NN],queries[NN];
bool cmp(pair<int,int> x,pair<int,int> y){
return min(x.F,x.S)>min(y.F,y.S);
}
int getpar(int x){
if (x==parr[x]) return x;
return parr[x]=getpar(parr[x]);
}
void link(int x,int y,int nw){
x=getpar(x);y=getpar(y);
a[nw]=min(a[x],a[y]);
if (x==y){
adj[nw].pb(x);
parr[x]=nw;
return;
}
adj[nw].pb(x);adj[nw].pb(y);
parr[x]=parr[y]=nw;
return;
}
void dfs(int x){
b[x]=t++;
sz[x]=1;
for (auto u:adj[x]){
par[0][u]=x;
dfs(u);
sz[x]+=sz[u];
}return;
}
bool cmpp(pair<int,int> x,pair<int,int> y){
return max(x.F,x.S)>max(y.F,y.S);
}
bool cmppp(vector<int> x,vector<int> y){
return x[3]<y[3];
}
void build(){
for (int i=0;i<22;i++) par[i][n+m]=n+m;
for (int i=1;i<22;i++){
for (int j=0;j<n+m;j++){
par[i][j]=par[i-1][par[i-1][j]];
}
}return;
}
int getparr(int x){
if (x==parrr[x]) return x;
return parrr[x]=getparr(parrr[x]);
}
void linkk(int x,int y){
x=getparr(x);y=getparr(y);
if (x==y) return;
if (comp[x].size()>comp[y].size()) swap(x,y);
for (auto u:comp[x]) comp[y].ep(u);
parrr[x]=y;
return;
}
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) {
n=N;m=X.size();q=L.size();
for (int i=0;i<n+m;i++) parr[i]=i;
for (int i=0;i<n;i++) a[i]=i;
vector<pair<int,int>> edges;
for (int i=0;i<m;i++) edges.pb({X[i],Y[i]});
sort(edges.begin(),edges.end(),cmp);
for (int i=0;i<m;i++) link(edges[i].F,edges[i].S,i+n);
par[0][n+m-1]=n+m;
dfs(n+m-1);
/*for (int i=0;i<n+m;i++){
cout<<i<<": ";
for (auto u:adj[i]) cout<<u<<' ';cout<<endl;
}
for (int i=0;i<n;i++) cout<<b[i]<<' ';cout<<endl;*/
vector<int> ans(q);
sort(edges.begin(),edges.end(),cmpp);
for (int i=0;i<q;i++) queries[i]={S[i],E[i],L[i],R[i],i};
sort(queries,queries+q,cmppp);
/*for (int i=0;i<q;i++){
for (auto u:queries[i]) cout<<u<<' ';
cout<<endl;
}
for (auto u:edges) cout<<u.F<<' '<<u.S<<endl;*/
build();
for (int i=0;i<n;i++) parrr[i]=i,comp[i].ep(b[i]);
for (int i=0;i<q;i++){
//cout<<"query "<<i<<endl;
while (!edges.empty() && max(edges.back().F,edges.back().S)<=queries[i][3]){
linkk(edges.back().F,edges.back().S);
//cout<<edges.back().F<<' '<<edges.back().S<<endl;
edges.ppb();
}
int x=queries[i][0];
for (int j=21;j>=0;j--){
if (par[j][x]==n+m) continue;
if (a[par[j][x]]<queries[i][2]) continue;
x=par[j][x];
}
int y=getparr(queries[i][1]);
//for (auto u:comp[y]) cout<<u<<' ';cout<<endl;
//cout<<x<<' '<<b[x]<<' '<<b[x]+sz[x]<<endl;
auto it=comp[y].lower_bound(b[x]);
if (it==comp[y].end()) continue;
if (*it<b[x]+sz[x]) ans[queries[i][4]]=1;
}
return ans;
}
