/**
* Author : boatinw99
* Date : 3.5.2019 15:42
*/
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std ;
typedef pair<int,int> pii ;
#define fi first
#define se second
const int N = 2e5+9 ,inf = 1e9 ;
struct Q
{
int st,ed,l,r,idx ;
}query[N];
unordered_map<int,int> mp[N];
vector<int> memb[N];
pii edge[N<<1] ;
int n,m,q,p1[N],p2[N],sz[N],up[N];
int find(int u)
{
while(p1[u])u=p1[u];
return u ;
}
void Union(int u,int v)
{
int mn = min(u,v);
u=find(u),v=find(v);
if(u==v)return ;
if(sz[u]>sz[v])swap(u,v);
p1[u]=v;
sz[v]+=sz[u];
up[u]=mn;
}
void constructdsu()
{
for(int i=1;i<=n;i++)
{
p2[i]=i;
sz[i]=1;
memb[i].push_back(i);
}
sort(edge+1,edge+1+m,[&](const pii a,const pii b){
return min(a.fi,a.se)>min(b.fi,b.se);});
for(int i=1;i<=m;i++)Union(edge[i].fi,edge[i].se);
for(int i=1;i<=n;i++)
{
int node = i , dist = inf ;
while(node)
{
mp[node][i]=dist;
dist=min(dist,up[node]);
node=p1[node];
}
}
}
void magic_Union(int u,int v)
{
u=p2[u],v=p2[v];
if(u==v)return ;
if(memb[u].size()>memb[v].size())swap(u,v);
for(auto it:memb[u])
{
p2[it]=v;
int node = it;
while(node)
{
auto its = mp[node].find(u);
if(its==mp[node].end())break ;
mp[node][v]=max(mp[node][v],its->se);
mp[node].erase(its);
node=p1[node];
}
memb[v].push_back(it);
}
}
vector<int> check_validity(int SZ,vector<int> X,vector<int> Y,
vector<int> S,vector<int> E,
vector<int> L,vector<int> R)
{
n=SZ;
m=X.size();
q=S.size();
vector<int> ans(q);
for(int i=1;i<=m;i++)edge[i]={X[i-1]+1,Y[i-1]+1};
for(int i=1;i<=q;i++)query[i]={S[i-1]+1,E[i-1]+1,L[i-1]+1,R[i-1]+1,i};
///Done preprocess
constructdsu();
sort(query+1,query+1+q,[&](const Q a,const Q b){
return a.r<b.r;});
sort(edge+1,edge+1+m,[&](const pii a,const pii b){
return max(a.fi,a.se)<max(b.fi,b.se);});
for(int i=1,j=1;i<=q;i++)
{
while(j<=m&&max(edge[j].fi,edge[j].se)<=query[i].r)
{
magic_Union(edge[j].fi,edge[j].se);
j++;
}
int st = query[i].st , ed = query[i].ed , mnup = inf , dist = 0;
if(p2[st]==p2[ed])
{
ans[query[i].idx-1]=1;
continue;
}
while(st)
{
dist=max(dist,min(mnup,mp[st][p2[ed]]));
mnup=min(mnup,up[st]);
st=p1[st];
if(dist>=query[i].l)
{
ans[query[i].idx-1]=1;
break;
}
}
}
return ans ;
}
