/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
//#include "werewolf.h"
using namespace std;
typedef long long ll;
const int N_MAX = 200000;
const int M_MAX = 400000;
const int Q_MAX = 200000;
int N, M, Q;
vector <vector <int>> adj;
struct DSU {
vector <int> ancestor;
vector <vector <int>> sons;
int cntNodes;
DSU () {
cntNodes = N;
ancestor = vector <int> (N, -1);
sons = vector <vector <int>> (N);
}
int findRoot (int u) {
return (ancestor[u] == -1 ? u : ancestor[u] = findRoot(ancestor[u]));
}
void join (int u, int v) {
u = findRoot(u);
v = findRoot(v);
if (u != v) {
int w = cntNodes++;
sons.push_back({});
ancestor.push_back(-1);
sons[w].push_back(u);
sons[w].push_back(v);
ancestor[u] = w;
ancestor[v] = w;
}
}
vector <pair <int, int>> range;
vector <int> order;
int currID;
void dfs (int u) {
if (sons[u].empty()) {
order.push_back(u);
range[u] = make_pair(currID, currID);
currID++;
} else {
range[u] = make_pair(INT_MAX, INT_MIN);
for (int v : sons[u]) {
dfs(v);
range[u].first = min(range[u].first, range[v].first);
range[u].second = max(range[u].second, range[v].second);
}
}
}
void linearize () {
range = vector <pair <int, int>> (cntNodes);
currID = 0;
dfs(cntNodes - 1);
}
};
vector <vector <int>> SGT;
void build (int node, int l, int r, vector <int> &arr) {
SGT[node].resize(r - l + 1);
if (l == r) {
SGT[node][0] = arr[l];
return;
}
int mid = (l + r) / 2;
int lSon = node * 2, rSon = node * 2 + 1;
build(lSon, l, mid, arr);
build(rSon, mid + 1, r, arr);
merge(SGT[lSon].begin(), SGT[lSon].end(), SGT[rSon].begin(), SGT[rSon].end(), SGT[node].begin());
}
void build (vector <int> &arr) {
SGT = vector <vector <int>> (N * 4);
build(1, 0, N - 1, arr);
}
bool query (int node, int l, int r, int ql, int qr, int mn, int mx) {
if (ql <= l && r <= qr) {
int lo = 0, hi = (int) SGT[node].size();
while (lo < hi) {
int avg = (lo + hi) / 2;
if (SGT[node][avg] < mn) {
lo = avg + 1;
} else {
hi = avg;
}
}
return (lo < (int) SGT[node].size() && SGT[node][lo] <= mx);
}
int mid = (l + r) / 2;
int lSon = node * 2, rSon = node * 2 + 1;
if (ql <= mid) {
if (query(lSon, l, mid, ql, qr, mn, mx) == true) {
return true;
}
}
if (mid + 1 <= qr) {
if (query(rSon, mid + 1, r, ql, qr, mn, mx) == true) {
return true;
}
}
return false;
}
bool query (int ql, int qr, int mn, int mx) {
return query(1, 0, N - 1, ql, qr, mn, mx);
}
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 = (int) X.size(); Q = (int) S.size();
adj = vector <vector <int>> (N);
for (int i = 0; i < M; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
vector <vector <int>> withL(N), withR(N);
for (int i = 0; i < Q; i++) {
withL[L[i]].push_back(i);
withR[R[i]].push_back(i);
}
vector <int> Lnode(Q), Rnode(Q);
DSU DSULarge;
for (int u = N - 1; u >= 0; u--) {
for (int v : adj[u]) {
if (u < v) {
DSULarge.join(u, v);
}
}
for (int i : withL[u]) {
Lnode[i] = DSULarge.findRoot(S[i]);
}
}
DSU DSUSmall;
for (int u = 0; u < N; u++) {
for (int v : adj[u]) {
if (v < u) {
DSUSmall.join(u, v);
}
}
for (int i : withR[u]) {
Rnode[i] = DSUSmall.findRoot(E[i]);
}
}
DSULarge.linearize();
DSUSmall.linearize();
vector <pair <int, int>> Lrange(Q), Rrange(Q);
for (int i = 0; i < Q; i++) {
Lrange[i] = DSULarge.range[Lnode[i]];
Rrange[i] = DSUSmall.range[Rnode[i]];
}
vector <int> arr(N);
for (int u = 0; u < N; u++) {
arr[DSULarge.range[u].first] = DSUSmall.range[u].first;
}
build(arr);
vector <int> answer(Q);
for (int i = 0; i < Q; i++) {
answer[i] = query(Lrange[i].first, Lrange[i].second, Rrange[i].first, Rrange[i].second);
}
return answer;
}
