#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
vector <int> adj[MAXN + 5][2];
vector <int> edges[MAXN + 5];
vector <pair<pair<int, int>, pair<int, int>>> queries[MAXN + 5];
int tin[MAXN + 5][2], tout[MAXN + 5][2], par[MAXN + 5][2];
int inv[MAXN + 5][2], up[MAXN + 5][20][2];
int t = 0;
int bit[MAXN + 5];
int N, Q, M;
void update(int idx, int val) {
for (; idx <= N; idx += idx & -idx) bit[idx] += val;
}
int get(int idx) {
int ans = 0;
for (; idx >= 1; idx -= idx & -idx) ans += bit[idx];
return ans;
}
int query(int l, int r) { return get(r) - get(l - 1); }
void dfs(int idx, int cur) {
tin[idx][cur] = ++t;
inv[t][cur] = idx;
// cout << idx << " " << t << "\n";
for (auto i : adj[idx][cur]) {
up[i][0][cur] = idx;
dfs(i, cur);
}
tout[idx][cur] = t;
}
int find(int idx, int cur) {
return par[idx][cur] == idx ? idx : par[idx][cur] = find(par[idx][cur], cur);
}
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;
Q = S.size();
M = X.size();
for (int i = 0; i < M; i++) {
edges[X[i]].push_back(Y[i]);
edges[Y[i]].push_back(X[i]);
}
for (int i = 0; i < N; i++) {
par[i][0] = par[i][1] = i;
}
for (int i = 0; i < N; i++) {
for (auto x : edges[i]) {
if (x < i) {
x = find(x, 0);
if (i != x) {
par[x][0] = i;
adj[i][0].push_back(x);
}
}
}
}
for (int i = N - 1; i >= 0; i--) {
for (auto x : edges[i]) {
if (x > i) {
x = find(x, 1);
if (i != x) {
par[x][1] = i;
adj[i][1].push_back(x);
}
}
}
}
t = 0;
up[N - 1][0][0] = N - 1;
dfs(N - 1, 0);
t = 0;
up[0][0][1] = 0;
dfs(0, 1);
for (int k = 0; k < 2; k++) {
for (int log = 1; log < 20; log++) {
for (int i = 0; i < N; i++) {
up[i][log][k] = up[up[i][log - 1][k]][log - 1][k];
}
}
}
auto binlift = [&](int idx, int batas, int cur) {
if (cur) {
for (int log = 19; log >= 0; --log) {
if (up[idx][log][cur] >= batas) {
idx = up[idx][log][cur];
}
}
}
else {
for (int log = 19; log >= 0; --log) {
if (up[idx][log][cur] <= batas) {
idx = up[idx][log][cur];
}
}
}
return idx;
};
for (int i = 0; i < Q; i++) {
// cari terjauh sehingga x >= Li
int x = binlift(S[i], L[i], 1);
int y = binlift(E[i], R[i], 0);
queries[tin[x][1] - 1].push_back({{tin[y][0], tout[y][0]}, {-1, i}});
queries[tout[x][1]].push_back({{tin[y][0], tout[y][0]}, {1, i}});
}
vector <int> ans(Q);
for (int i = 1; i <= N; i++) {
update(tin[inv[i][1]][0], 1);
for (auto [range, val] : queries[i]) {
auto [l, r] = range;
auto [add, j] = val;
ans[j] += add * query(l, r);
}
}
for (int i = 0; i < Q; i++) ans[i] = bool(ans[i]);
return ans;
}
