#include <bits/stdc++.h>
#define ll long long
#define db long double
#define maxn 200005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x)
using namespace std;
#include "werewolf.h"
int r[maxn],n,m,i,q,u,v,mi[maxn],ma[maxn],Begin[maxn],End[maxn],cnt,p_inc[maxn][21],p_dec[maxn][21];
set <int> s[maxn];
vector <int> a[maxn],a_inc[maxn],a_dec[maxn];
vector <II> query[maxn];
vector <int> check_validity(int n,vector <int> U,vector <int> V,vector <int> S,vector <int> T,vector <int> L,vector <int> R)
{
m=U.size(); q=S.size();
for(i=0;i<m;i++) U[i]++,V[i]++;
for(i=0;i<q;i++) S[i]++,T[i]++,L[i]++,R[i]++;
for(i=0;i<m;i++)
{
u=U[i]; v=V[i];
// cerr<<u<<" "<<v<<'\n';
a[u].push_back(v); a[v].push_back(u);
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Build Inc_Tree
function <int(int)> root=[&](int u)
{
return u==r[u] ? u : r[u]=root(r[u]);
};
auto join_inc=[&](int u,int v)
{
u=root(u); v=root(v);
if(u==v) return ;
if(mi[u]>mi[v]) swap(u,v);
a_inc[mi[u]].push_back(mi[v]);
mi[v]=mi[u];
r[u]=v;
};
for(u=1;u<=n;u++) r[u]=mi[u]=u;
for(u=n;u>=1;u--)
for(int v:a[u])
if(v>u) join_inc(u,v);
auto join_dec=[&](int u,int v)
{
u=root(u); v=root(v);
if(u==v) return ;
if(ma[u]<ma[v]) swap(u,v);
a_dec[ma[u]].push_back(ma[v]);
ma[v]=ma[u];
r[u]=v;
};
for(u=n;u>=1;u--) r[u]=ma[u]=u;
for(u=1;u<=n;u++)
for(int v:a[u])
if(v<u) join_dec(u,v);
function <void(int)> dfs_inc=[&](int u)
{
Begin[u]=++cnt;
for(int i=1;(1<<i)<=n;i++)
p_inc[u][i]=p_inc[p_inc[u][i-1]][i-1];
for(int v:a_inc[u])
{
// cerr<<u<<" "<<v<<'\n';
p_inc[v][0]=u;
dfs_inc(v);
}
End[u]=cnt;
};
function <void(int)> dfs_dec=[&](int u)
{
for(int i=1;(1<<i)<=n;i++)
p_dec[u][i]=p_dec[p_dec[u][i-1]][i-1];
for(int v:a_dec[u])
{
// cerr<<u<<" "<<v<<'\n';
p_dec[v][0]=u;
dfs_dec(v);
}
};
dfs_inc(1);
dfs_dec(n);
vector <int> res(q);
function <void(int)> DFS=[&](int u)
{
s[u].insert(Begin[u]);
for(int v:a_dec[u])
{
DFS(v);
if(s[u].size()<s[v].size()) s[u].swap(s[v]);
for(int k:s[v]) s[u].insert(k);
}
for(II x:query[u])
res[x.snd]=(s[u].lower_bound(Begin[x.fst])!=s[u].upper_bound(End[x.fst]));
};
for(i=0;i<q;i++)
{
u=S[i]; v=T[i];
for(int j=Log(n);j>=0;j--)
if(p_inc[u][j]>=L[i]) u=p_inc[u][j];
for(int j=Log(n);j>=0;j--)
if(p_dec[v][j]>0 && p_dec[v][j]<=R[i]) v=p_dec[v][j];
query[v].push_back({ u,i });
}
DFS(n);
return res;
}
/*
int main()
{
freopen("werewolf.inp","r",stdin);
freopen("werewolf.out","w",stdout);
int n,m,q,u,v,s,t,l,r,i;
cin>>n>>m>>q;
vector <int> U,V,S,T,L,R;
for(i=1;i<=m;i++) cin>>u>>v,U.push_back(u),V.push_back(v);
for(i=1;i<=q;i++) cin>>s>>t>>l>>r,S.push_back(s),T.push_back(t),L.push_back(l),R.push_back(r);
vector <int> vec=check_validity(n,U,V,S,T,L,R);
for(i=0;i<q;i++) cout<<vec[i]<<" ";
}
*/
