#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, sp[1] -> max
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;
}
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) {
int node = i;
act[node] = 1;
while (1) {
for (int v: ad[node]) {
if (!act[v]) {
act[v] = act[node] + 1;
node = v;
break;
}
}
if (ad[node].size() == 1) break;
}
break;
}
}
for (int i = 0; i < N; i++){
sp[0][act[i]][0] = i;
sp[1][act[i]][0] = 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]);
}
}
for (int i = 0; i < Q; ++i) {
int n1 = act[S[i]], n2 = act[E[i]];
if (n1 < n2){
int l = n1, r = n2, f1 = -1, f2 = 1e9;
while (l <= r) {
int mid = (l + r) / 2;
if (query0(n1, mid) >= L[i]) {
f1 = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
l = n1, r = n2;
while (l <= r) {
int mid = (l + r) / 2;
if (query1(mid, n2) <= R[i]) {
f2 = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
A[i] = (f1 >= f2);
}
else {
swap(n1, n2);
int l = n1, r = n2, f1 = -1, f2 = 1e9;
while (l <= r) {
int mid = (l + r) / 2;
if (query1(n1, mid) <= R[i]) {
f1 = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
l = n1, r = n2;
while (l <= r) {
int mid = (l + r) / 2;
if (query0(mid, n2) >= L[i]) {
f2 = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
A[i] = (f1 >= f2);
}
}
}
return A;
}
