#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> lab;
DSU(int n) {
lab.assign(n + 1, -1);
}
int merge(int a, int b) {
if (lab[a] > lab[b]) {
swap(a, b);
}
lab[a] += lab[b];
lab[b] = a;
return a;
}
int getRoot(int a) {
while (lab[a] >= 0) a = lab[a];
return a;
}
};
struct DSUTree {
struct Node {
int tin, tout, weight;
vector<int> child;
};
int n, TIME = 0;
vector<array<int, 3>> edges;
vector<int> root, eulerTour;
vector<vector<int>> par;
vector<Node> nodes;
DSUTree(int n): n(n) {
root.resize(n + 1);
nodes.resize(2 * n);
par.assign(2 * n, vector<int>(20));
}
void addEdge(int u, int v, int c) {
edges.push_back({c, u, v});
}
void construct() {
sort(edges.begin(), edges.end());
DSU dsu(n);
for (int i = 1; i <= n; i++) {
root[i] = i;
nodes[i].weight = -1e9;
}
int cnt = n;
for (auto e: edges) {
int a = dsu.getRoot(e[1]);
int b = dsu.getRoot(e[2]);
if (a == b) continue;
int root1 = root[a], root2 = root[b];
a = dsu.merge(a, b);
root[a] = ++cnt;
nodes[cnt].child.push_back(root1);
nodes[cnt].child.push_back(root2);
nodes[cnt].weight = e[0];
par[root1][0] = cnt;
par[root2][0] = cnt;
}
dfs(2 * n - 1);
getOrder();
for (int i = 1; i < 20; i++) {
for (int j = 1; j <= 2 * n - 1; j++) {
par[j][i] = par[par[j][i - 1]][i - 1];
}
}
}
void dfs(int u) {
nodes[u].tin = ++TIME;
eulerTour.push_back(u);
for (auto i: nodes[u].child) {
dfs(i);
}
nodes[u].tout = ++TIME;
eulerTour.push_back(u);
}
vector<int> order;
void getOrder() {
vector<int> vs(2 * n + 1);
for (auto i: eulerTour) {
if (i <= n && vs[i] == 0) {
order.push_back(i);
}
vs[i] = 1;
}
}
// return the interval that s can reach through edges <= r
pair<int, int> getInterval(int s, int r) {
// find farthest parent has weight <= r
for (int i = 19; i >= 0; i--) {
int p = par[s][i];
if (p && nodes[p].weight <= r) {
s = p;
}
}
// find [l, r] such that tin[s] <= tin[i] <= tout[s]
int lower = 0, upper = n - 1;
while (lower < upper) {
int mid = (lower + upper) / 2;
if (nodes[s].tin <= nodes[order[mid]].tin) {
upper = mid;
}
else {
lower = mid + 1;
}
}
int l = lower;
lower = 0, upper = n - 1;
while (lower < upper) {
int mid = (lower + upper + 1) / 2;
if (nodes[s].tout >= nodes[order[mid]].tin) {
lower = mid;
}
else {
upper = mid - 1;
}
}
return {l, lower};
}
};
std::vector<int> check_validity(int n, std::vector<int> x, std::vector<int> y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
int m = x.size(), q = S.size();
DSUTree maxTree(n), minTree(n);
for (int i = 1; i <= m; i++) {
int u = x[i - 1], v = y[i - 1];
u++; v++;
maxTree.addEdge(u, v, -min(u, v)); // >= l
minTree.addEdge(u, v, max(u, v)); // <= r
}
minTree.construct();
maxTree.construct();
vector<int> a = minTree.order;
vector<int> b = maxTree.order;
vector<int> pos(n + 1), c(n + 1);
// for (auto i: a) cout << i << " ";
// cout << endl;
// for (auto i: b) cout << i << " ";
// cout << endl;
for (int i = 0; i < n; i++) {
pos[a[i]] = i + 1;
}
for (int i = 0; i < n; i++) {
c[i + 1] = pos[b[i]];
}
vector<int> ret;
for (int i = 0; i < q; i++) {
int s = S[i], e = E[i], l = L[i], r = R[i];
// cin >> s >> e >> l >> r;
s++; e++; l++; r++;
auto [l1, r1] = minTree.getInterval(e, r);
auto [l2, r2] = maxTree.getInterval(s, -l);
// cout << l1 << " " << r1 << " " << l2 << " " << r2 << endl;
vector<int> vs(n + 1);
for (int i = l1; i <= r1; i++) {
vs[a[i]]++;
}
int res = 0;
for (int i = l2; i <= r2; i++) {
if (vs[b[i]]) res = 1;
}
// cout << res << '\n';
ret.push_back(res);
}
return ret;
}
