#include <bits/stdc++.h>
using namespace std;
#define in(i) cin >> i
#define out(o) cout << o
vector<int> parent;
vector<int> sz;
int find(int v) {
if (v == parent[v]) return v;
return parent[v] = find(parent[v]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (sz[a] > sz[b]) swap(a, b);
parent[a] = b;
sz[b] += sz[a];
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int M = X.size(); // = Y.size()
int Q = S.size(); // = E.size() = L.size() = R.size()
parent.resize(N);
sz.resize(N, 1);
vector<int> ans(Q);
if (N <= 3000 && M <= 6000 && Q <= 3000) {
// S1, S2
for (int i = 0; i < Q; i++) {
int l = L[i];
int r = R[i];
int s = S[i];
int e = E[i];
for (int j = 0; j < N; j++) parent[j] = j, sz[j] = 1;
for (int j = 0; j < M; j++) {
int x = X[j];
int y = Y[j];
if (l <= min(x, y)) unite(x, y);
}
vector<int> works(N, 0);
for (int j = 0; j < N; j++) if (find(s) == find(j)) works[j]++;
for (int j = 0; j < N; j++) parent[j] = j, sz[j] = 1;
for (int j = 0; j < M; j++) {
int x = X[j];
int y = Y[j];
if (r >= max(x, y)) unite(x, y);
}
for (int j = 0; j < N; j++) if (find(e) == find(j)) works[j]++;
ans[i] = +(*max_element(works.begin(), works.end()) == 2);
}
} else {
// S3 assumed, if S4 then segfault or sth
vector<vector<int>> adjList;
for (int i = 0; i < M; i++) {
int x = X[i];
int y = Y[i];
adjList[x].push_back(y);
adjList[y].push_back(x);
}
int v = 0;
int prev = -1;
while (adjList[v].size() == 2) {
if (adjList[v][0] == prev) {
prev = v;
v = adjList[v][1];
} else {
prev = v;
v = adjList[v][0];
}
}
vector<int> order;
order.push_back(v);
prev = -1;
do {
if (adjList[v][0] == prev) {
prev = v;
v = adjList[v][1];
} else {
prev = v;
v = adjList[v][0];
}
order.push_back(v);
} while (adjList[v].size() == 2);
vector<int> ind(N);
for (int i = 0; i < N; i++) {
ind[order[i]] = i;
}
vector<int> left(Q);
vector<int> right(Q);
vector<array<int, 4>> human;
vector<array<int, 4>> wolf;
// {determiner, node, query index, left or right}. left = 0, right = 1.
for (int i = 0; i < Q; i++) {
int l = L[i];
int r = R[i];
int s = S[i];
int e = E[i];
int u = ind[s];
int v = ind[e];
if (u < v) {
human.push_back({l, u, i, 1});
wolf.push_back({r, v, i, 0});
} else {
human.push_back({l, u, i, 0});
wolf.push_back({r, v, i, 1});
}
}
sort(human.begin(), human.end());
sort(wolf.rbegin(), wolf.rend());
set<int> less;
int ptr = 0;
for (int i = 0; i < N; i++) {
while (ptr < Q && human[ptr][0] <= i) {
int l = human[ptr][0];
int u = human[ptr][1];
int j = human[ptr][2];
int dir = human[ptr][3];
if (dir) {
auto it = less.lower_bound(u);
if (it == less.end()) right[j] = N + 5;
else right[j] = (*it) - 1;
} else {
auto it = less.lower_bound(u);
if (it == less.begin()) left[j] = -5;
else left[j] = (*--it) + 1;
}
ptr++;
}
less.insert(ind[i]);
}
set<int> more;
ptr = 0;
for (int i = N - 1; i >= 0; i--) {
while (ptr < Q && wolf[ptr][0] >= i) {
int l = wolf[ptr][0];
int u = wolf[ptr][1];
int j = wolf[ptr][2];
int dir = wolf[ptr][3];
if (dir) {
auto it = more.lower_bound(u);
if (it == more.end()) right[j] = N + 5;
else right[j] = (*it) - 1;
} else {
auto it = more.lower_bound(u);
if (it == more.begin()) left[j] = -5;
else left[j] = (*--it) + 1;
}
ptr++;
}
more.insert(ind[i]);
}
for (int i = 0; i < Q; i++) {
ans[i] = +(left[i] <= right[i]);
}
}
return ans;
}
