#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 200010;
int N, M, Q;
vector<int> adj[MAXN];
int par[MAXN];
const int MAXL = 20;
int anc[2][MAXL][MAXN];
vector<int> tr[MAXN];
void reset() {
fill_n(par, N, -1);
for (int i = 0; i < N; i++) tr[i].clear();
}
int getpar(int a) {
return par[a] == -1 ? a : par[a] = getpar(par[a]);
}
int st[MAXN], ed[MAXN];
int ind;
void dfs(int cur = 0) {
st[cur] = ind++;
for (int nxt : tr[cur]) {
dfs(nxt);
}
ed[cur] = ind;
}
const int MAXQ = 200010;
vector<int> queries[MAXN];
int ql[MAXQ], qr[MAXQ];
vector<int> ans;
struct seg {
seg* ch[2] = {nullptr, nullptr};
};
void update(int p, seg* &n, int x = 0, int y = N) {
if (!n) {
n = new seg();
}
if (y - x > 1) {
int z = (x + y) / 2;
if (p < z) {
update(p, n->ch[0], x, z);
} else {
update(p, n->ch[1], z, y);
}
}
}
int query(int l, int r, seg* n, int x = 0, int y = N) {
if (!n) {
return 0;
}
if (l <= x && y <= r) {
return 1;
} else {
int z = (x + y) / 2;
if (l < z && query(l, r, n->ch[0], x, z)) return 1;
if (z < r && query(l, r, n->ch[1], z, y)) return 1;
return 0;
}
}
seg* merge(seg* a, seg* b) {
if (!a) return b;
if (!b) return a;
a->ch[0] = merge(a->ch[0], b->ch[0]);
a->ch[1] = merge(a->ch[1], b->ch[1]);
return a;
}
seg* roots[MAXN];
void go(int cur = N - 1) {
for (int nxt : tr[cur]) {
go(nxt);
roots[cur] = merge(roots[cur], roots[nxt]);
}
update(st[cur], roots[cur]);
for (int q : queries[cur]) {
ans[q] = query(ql[q], qr[q], roots[cur]);
}
}
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) {
N = n;
M = int(X.size());
Q = int(S.size());
for (int i = 0; i < M; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
reset();
for (int a = N - 1; a >= 0; a--) {
for (int b : adj[a]) {
if (b < a) continue;
int t = getpar(b);
if (a != t) {
par[t] = a;
anc[0][0][t] = a;
tr[a].push_back(t);
}
}
}
anc[0][0][0] = -1;
dfs();
reset();
for (int a = 0; a < N; a++) {
for (int b : adj[a]) {
if (b > a) continue;
int t = getpar(b);
if (a != t) {
par[t] = a;
anc[1][0][t] = a;
tr[a].push_back(t);
}
}
}
anc[1][0][N - 1] = -1;
for (int t = 0; t < 2; t++) {
for (int l = 1; l < MAXL; l++) {
for (int i = 0; i < N; i++) {
if (anc[t][l - 1][i] == -1) {
anc[t][l][i] = -1;
} else {
anc[t][l][i] = anc[t][l - 1][anc[t][l - 1][i]];
}
}
}
}
for (int q = 0; q < Q; q++) {
int a = S[q], b = E[q];
for (int l = MAXL - 1; l >= 0; l--) {
if (anc[0][l][a] != -1 && anc[0][l][a] >= L[q]) {
a = anc[0][l][a];
}
}
for (int l = MAXL - 1; l >= 0; l--) {
if (anc[1][l][b] != -1 && anc[1][l][b] <= R[q]) {
b = anc[1][l][b];
}
}
ql[q] = st[a];
qr[q] = ed[a];
queries[b].push_back(q);
}
ans = vector<int>(Q);
go();
return ans;
}
