#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int maxn_12 = 3e3 + 2;
const int maxn_3 = 2e5 + 2;
const int lg = 19;
vector <int> ad [maxn_3];
bitset <maxn_12> vis1, vis2;
int act[maxn_3];
int sp[2][maxn_3][lg]; // sp[0] -> min r, sp[1] -> max l
void dfs1 (int u, int l, int r) {
vis1[u] = 1;
for (int v: ad[u]) {
if (v < l || vis1[v]) continue;
dfs1(v, l, r);
}
}
int dfs2 (int u, int l, int r) {
vis2[u] = 1;
bool b = (vis1[u]);
for (int v: ad[u]) {
if (v > r || vis2[v]) continue;
b|=dfs2(v, l, r);
}
return b;
}
void label (int u, int p, int nr) {
act[u] = nr;
for (int v: ad[u]) {
if (v == p) continue;
label(v, u, nr + 1);
}
}
int query0 (int l, int r) {
int k = log2(r - l + 1);
return min(sp[0][l][k], sp[0][r - (1 << k) + 1][k]);
}
int query1 (int l, int r) {
int k = log2(r - l + 1);
return max(sp[1][l][k], sp[1][r - (1 << k) + 1][k]);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
for (int i = 0; i < X.size(); i++){
ad[X[i]].push_back(Y[i]);
ad[Y[i]].push_back(X[i]);
}
int Q = S.size();
vector<int> A(Q);
if (N <= 3000 && Q <= 3000 && X.size() <= 6000){
for (int i = 0; i < Q; ++i) {
vis1 = vis2 = 0;
dfs1(S[i], L[i], R[i]);
A[i] = dfs2(E[i], L[i], R[i]);
}
}
else {
for (int i = 0; i < N; i++){
if (ad[i].size() == 1) {
label(i, -1, 0);
}
for (int i = 0; i < N; i++){
sp[0][i][0] = R[act[i]];
sp[1][i][0] = L[act[i]];
}
for (int k = 1; k < lg; k++){
for (int i = 0; i + (1 << k) - 1 < N; i++){
sp[0][i][k] = min(sp[0][i][k-1], sp[0][i + (1 << (k - 1))][k-1]);
sp[1][i][k] = max(sp[1][i][k-1], sp[1][i + (1 << (k - 1))][k-1]);
}
}
}
}
return A;
}
