#include <stdio.h>
#include <math.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
#include <string>
#include <unordered_map>
#include <map>
#include <queue>
#include <set>
#include <stack>
using namespace std;
#define long long long
#define fi first
#define se second
typedef pair<int,int> ii;
int n, m, q;
int L[200003], R[200003], S[200003], E[200003];
bool visited[200003][2];
vector<int> vec[200003];
void dfs(int u, int x, int l, int r)
{
// printf("%d %d %d %d\n", u, x, l, r);
visited[u][x] = 1;
if(x == 0 && !visited[u][1] && l <= u && u <= r)
dfs(u,1, l, r);
for(int v : vec[u])
{
if(x == 0 && v >= l && !visited[v][0])
dfs(v,0, l, r);
if(x == 1 && v <= r && !visited[v][1])
dfs(v,1, l, r);
}
}
vector<int> solve_small()
{
vector<int> ans;
for(int i = 0; i < q; i++)
{
for(int j = 0; j < n; j++)
visited[j][0] = visited[j][1] = 0;
dfs(S[i], 0, L[i], R[i]);
ans.push_back(visited[E[i]][1]);
}
return ans;
}
int A[200003];
int id[200003];
int sz = 0;
int Tx[200003][20], Tn[200003][20];
int lg[200003];
void create_line(int u)
{
visited[u][0] = 1;
A[sz] = u;
id[u] = sz++;
for(int v : vec[u])
if(!visited[v][0])
create_line(v);
}
void build()
{
for(int i = 1; i <= 200000; i++)
lg[i] = log2(i);
for(int i = 0; i < 20; i++)
for(int j = 0; j+(1<<i)-1 < n; j++)
Tn[j][i] = (i == 0)? A[j] : min(Tn[j][i-1], Tn[j+(1<<(i-1))][i-1]);
for(int i = 0; i < 20; i++)
for(int j = 0; j+(1<<i)-1 < n; j++)
Tx[j][i] = (i == 0)? A[j] : max(Tx[j][i-1], Tx[j+(1<<(i-1))][i-1]);
}
int MAX(int kir, int kan)
{
int len = kan-kir+1;
int x = lg[len];
return max(Tx[kir][x], Tx[kan-(1<<x)+1][x]);
}
int MIN(int kir, int kan)
{
int len = kan-kir+1;
int x = lg[len];
return min(Tn[kir][x], Tn[kan-(1<<x)+1][x]);
}
vector<int> solve_line()
{
vector<int> ans;
for(int i = 0; i < n; i++)
{
if(vec[i].size() == 1)
{
create_line(i);
break;
}
}
build();
// for(int i = 0; i < n; i++) printf("%d ", A[i]); printf("\n");
// for(int i = 0; i < n; i++) printf("%d ", id[i]); printf("\n");
for(int i = 0; i < q; i++)
{
int x = id[S[i]], y = id[E[i]];
// printf("%d %d\n", x, y);
int kir1 = 0, kan1 = x;
while(kir1 < kan1)
{
int mid = (kir1+kan1)/2;
if(MIN(mid, x) >= L[i]) kan1 = mid;
else kir1 = mid+1;
}
int kir2 = x, kan2 = n-1;
while(kir2 < kan2)
{
int mid = (1+kir2+kan2)/2;
if(MIN(x, mid) >= L[i]) kir2 = mid;
else kan2 = mid-1;
}
int kir3 = 0, kan3 = y;
while(kir3 < kan3)
{
int mid = (kir3+kan3)/2;
if(MAX(mid, y) <= R[i]) kan3 = mid;
else kir3 = mid+1;
}
int kir4 = y, kan4 = n-1;
while(kir4 < kan4)
{
int mid = (1+kir4+kan4)/2;
if(MAX(y, mid) <= R[i]) kir4 = mid;
else kan4 = mid-1;
}
if(kir4 < kir1 || kir2 < kir3) ans.push_back(0);
else ans.push_back(1);
}
return ans;
}
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++)
{
vec[X[i]].push_back(Y[i]);
vec[Y[i]].push_back(X[i]);
}
for(int i = 0; i < q; i++)
S[i] = _S[i], L[i] = _L[i], R[i] = _R[i], E[i] = _E[i];
if(n <= 3000 && m <= 6000 && q <= 3000) return solve_small();
else return solve_line();
}
