#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
const int MAXN = 200005;
struct KRT {
int n, timer;
vector<int> adj[MAXN * 2];
int st[MAXN * 2], en[MAXN * 2], parent[MAXN * 2][20];
void dfs(int u) {
st[u] = ++timer;
for (int i = 1; i < 20; i++) parent[u][i] = parent[parent[u][i - 1]][i - 1];
for (int v : adj[u]) {
parent[v][0] = u;
dfs(v);
}
en[u] = timer;
}
int get_root(int u, int val, bool is_human) {
for (int i = 19; i >= 0; i--) {
if (parent[u][i] != 0) {
if (is_human && parent[u][i] >= val) u = parent[u][i];
else if (!is_human && parent[u][i] <= val) u = parent[u][i];
}
}
return u;
}
};
struct DSU {
vector<int> p;
DSU(int n) : p(n + 1) { iota(p.begin(), p.end(), 0); }
int find(int i) { return p[i] == i ? i : p[i] = find(p[i]); }
void unite(int i, int j) { p[find(i)] = find(j); }
};
// 2D Range Query uchun Fenwick Tree
int bit[MAXN * 2];
void update(int i, int v) { for (; i < MAXN * 2; i += i & -i) bit[i] += v; }
int query(int i) { int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }
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(), Q = S.size();
KRT human, wolf;
vector<vector<int>> g(N);
for (int i = 0; i < M; i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
// Inson daraxtini qurish (N-1 dan 0 gacha)
DSU dsu_h(N);
for (int i = N - 1; i >= 0; i--) {
for (int v : g[i]) {
if (v > i && dsu_h.find(v) != i) {
human.adj[i].push_back(dsu_h.find(v));
dsu_h.unite(v, i);
}
}
}
human.timer = 0; human.dfs(0);
// Bo'ri daraxtini qurish (0 dan N-1 gacha)
DSU dsu_w(N);
for (int i = 0; i < N; i++) {
for (int v : g[i]) {
if (v < i && dsu_w.find(v) != i) {
wolf.adj[i].push_back(dsu_w.find(v));
dsu_w.unite(v, i);
}
}
}
wolf.timer = 0; wolf.dfs(N - 1);
// 2D nuqtalar: (human_st[i], wolf_st[i])
vector<int> p_idx(N + 1);
for (int i = 0; i < N; i++) p_idx[human.st[i]] = wolf.st[i];
vector<int> ans(Q, 0);
struct Query { int l, r, d, u, id; };
vector<Query> queries;
for (int i = 0; i < Q; i++) {
int u = human.get_root(S[i], L[i], true);
int v = wolf.get_root(E[i], R[i], false);
queries.push_back({human.st[u], human.en[u], wolf.st[v], wolf.en[v], i});
}
// Offline so'rovlarni ishlash (Sweep-line)
vector<pair<int, int>> events[MAXN * 2];
for (int i = 0; i < Q; i++) {
events[queries[i].l - 1].push_back({i, -1});
events[queries[i].r].push_back({i, 1});
}
for (int i = 1; i <= N; i++) {
update(p_idx[i], 1);
for (auto& ev : events[i]) {
int qid = ev.first;
int type = ev.second;
int cnt = query(queries[qid].u) - query(queries[qid].d - 1);
if (type == 1) ans[qid] += cnt;
else ans[qid] -= cnt;
}
}
for (int i = 0; i < Q; i++) ans[i] = (ans[i] > 0);
return ans;
}
