#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200005, LOGN = 20;
vector<int> adj1[N+5], adj2[N+5];
int up1[N+5][LOGN], up2[N+5][LOGN], in1[N+5], out1[N+5], in2[N+5], out2[N+5];
int timer1, timer2;
struct DSU {
vector<int> par;
DSU(int n) {
par.resize(n);
for(int i = 0; i < n; i++) par[i] = i;
}
int find_set(int v) {
return (v == par[v]) ? v : (par[v] = find_set(par[v]));
}
};
struct BIT {
int n;
vector<int> tree;
BIT(int n) : n(n), tree(n + 1, 0) {}
void add(int i, int delta) {
for (; i <= n; i += i & -i) tree[i] += delta;
}
int query(int i) {
int sum = 0;
for (; i > 0; i -= i & -i) sum += tree[i];
return sum;
}
};
struct QueryEvent {
int l2, r2, q_idx, sign;
};
// Hàm DFS cho cây 1
void dfs1(int u, int p) {
in1[u] = ++timer1;
up1[u][0] = p;
for (int i = 1; i < LOGN; ++i) {
if (up1[u][i - 1] != -1)
up1[u][i] = up1[up1[u][i - 1]][i - 1];
else
up1[u][i] = -1;
}
for (int v : adj1[u]) {
dfs1(v, u);
}
out1[u] = timer1;
}
// Hàm DFS cho cây 2
void dfs2(int u, int p) {
in2[u] = ++timer2;
up2[u][0] = p;
for (int i = 1; i < LOGN; ++i) {
if (up2[u][i - 1] != -1)
up2[u][i] = up2[up2[u][i - 1]][i - 1];
else
up2[u][i] = -1;
}
for (int v : adj2[u]) {
dfs2(v, u);
}
out2[u] = timer2;
}
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();
// Reset biến toàn cục cho mỗi lần gọi
timer1 = timer2 = 0;
for(int i = 0; i < N; ++i) {
adj1[i].clear(); adj2[i].clear();
for(int j = 0; j < LOGN; j++) up1[i][j] = up2[i][j] = -1;
}
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]);
// Xây dựng cây KRT 1
DSU dsu1(N);
for (int u = N - 1; u >= 0; u--) {
for (int v : g[u]) {
if (v > u) {
int root_v = dsu1.find_set(v);
if (root_v != u) {
adj1[u].push_back(root_v);
dsu1.par[root_v] = u;
}
}
}
}
// Xây dựng cây KRT 2
DSU dsu2(N);
for (int u = 0; u < N; u++) {
for (int v : g[u]) {
if (v < u) {
int root_v = dsu2.find_set(v);
if (root_v != u) adj2[u].push_back(root_v), dsu2.par[root_v] = u;
}
}
}
vector<int> is_root1(N, 1), is_root2(N, 1);
for (int i = 0; i < N; ++i) {
for (int v : adj1[i]) is_root1[v] = 0;
for (int v : adj2[i]) is_root2[v] = 0;
}
for (int i = 0; i < N; ++i) {
if (is_root1[i]) dfs1(i, -1);
if (is_root2[i]) dfs2(i, -1);
}
vector<vector<QueryEvent>> events(N + 1);
vector<int> pos_in_tree2(N + 1);
for (int i = 0; i < N; ++i) pos_in_tree2[in1[i]] = in2[i];
for (int i = 0; i < Q; ++i) {
int u = S[i], v = E[i];
for (int j = LOGN - 1; j >= 0; --j)
if (up1[u][j] != -1 && up1[u][j] >= L[i]) u = up1[u][j];
for (int j = LOGN - 1; j >= 0; --j)
if (up2[v][j] != -1 && up2[v][j] <= R[i]) v = up2[v][j];
int q_l1 = in1[u], q_r1 = out1[u];
int q_l2 = in2[v], q_r2 = out2[v];
if (q_l1 > 1) events[q_l1 - 1].push_back({q_l2, q_r2, i, -1});
events[q_r1].push_back({q_l2, q_r2, i, 1});
}
BIT bit(N);
vector<int> ans(Q, 0);
for (int x = 1; x <= N; ++x) {
bit.add(pos_in_tree2[x], 1);
for (auto &e : events[x])
ans[e.q_idx] += e.sign * (bit.query(e.r2) - bit.query(e.l2 - 1));
}
vector<int> res(Q);
for (int i = 0; i < Q; ++i) res[i] = (ans[i] > 0);
return res;
}
