#include <bits/stdc++.h>
#include "werewolf.h"
template <class T> using Vec = std::vector<T>;
struct RMQ {
Vec<Vec<int>> mintable;
Vec<Vec<int>> maxtable;
RMQ(const Vec<int>& vec) {
const int n = (int) vec.size();
int k = 0;
while ((1 << k) <= n) {
k += 1;
}
mintable.resize(k);
maxtable.resize(k);
mintable[0] = vec;
maxtable[0] = vec;
for (int h = 0; h < k - 1; ++h) {
const int len = n - (1 << (h + 1)) + 1;
mintable[h + 1].resize(len);
maxtable[h + 1].resize(len);
for (int i = 0; i < len; ++i) {
mintable[h + 1][i] = std::min(mintable[h][i], mintable[h][i + (1 << h)]);
maxtable[h + 1][i] = std::max(maxtable[h][i], maxtable[h][i + (1 << h)]);
}
}
}
int min(const int l, const int r) const {
if (l == r) {
return std::numeric_limits<int>::max();
}
const int h = 31 - __builtin_clz(r - l);
return std::min(mintable[h][l], mintable[h][r - (1 << h)]);
}
int max(const int l, const int r) const {
if (l == r) {
return std::numeric_limits<int>::min();
}
const int h = 31 - __builtin_clz(r - l);
return std::max(maxtable[h][l], maxtable[h][r - (1 << h)]);
}
};
template <class Func> int binary_search(int ok, int ng, const Func& f) {
while (std::abs(ok - ng) > 1) {
const int md = (ok + ng) / 2;
(f(md) ? ok : ng) = md;
}
return ok;
}
Vec<int> check_validity(int N, Vec<int> X, Vec<int> Y, Vec<int> S, Vec<int> E, Vec<int> L, Vec<int> R) {
const int M = (int) X.size();
const int Q = (int) S.size();
Vec<Vec<int>> graph(N);
for (int i = 0; i < M; ++i) {
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
if (N <= 3000 and M <= 6000 and Q <= 3000) {
Vec<int> ret(Q);
for (int i = 0; i < Q; ++i) {
Vec<char> state(N);
Vec<int> que;
que.reserve(N);
{
const auto push = [&](const int u) {
if (u >= L[i] and !(state[u] & 1)) {
state[u] |= 1;
que.push_back(u);
}
};
push(S[i]);
while (!que.empty()) {
const auto u = que.back();
que.pop_back();
for (const auto v : graph[u]) {
push(v);
}
}
}
{
const auto push = [&](const int u) {
if (u <= R[i] and !(state[u] & 2)) {
state[u] |= 2;
que.push_back(u);
}
};
push(E[i]);
while (!que.empty()) {
const auto u = que.back();
que.pop_back();
for (const auto v : graph[u]) {
push(v);
}
}
}
ret[i] = std::any_of(state.begin(), state.end(), [&](const int x) { return x == 3; });
}
return ret;
} else {
Vec<int> line;
line.reserve(N);
{
int u = 0;
while ((int) graph[u].size() != 1) {
u += 1;
}
Vec<char> done(N);
while (!done[u]) {
line.push_back(u);
done[u] = true;
for (const auto v : graph[u]) {
if (!done[v]) {
u = v;
break;
}
}
}
}
Vec<int> idx(N);
for (int i = 0; i < N; ++i) {
idx[line[i]] = i;
}
RMQ rmq(line);
Vec<int> ret(Q);
for (int i = 0; i < Q; ++i) {
const int u = S[i];
const int v = E[i];
if (idx[u] < idx[v]) {
const auto right = binary_search(idx[u], N, [&](const int r) {
return rmq.min(idx[u], r + 1) >= L[i];
});
const auto left = binary_search(idx[v], -1, [&](const int l) {
return rmq.max(l, idx[v] + 1) <= R[i];
});
ret[i] = right >= left;
} else {
const auto left = binary_search(idx[u], -1, [&](const int l) {
return rmq.min(l, idx[u] + 1) >= L[i];
});
const auto right = binary_search(idx[v], N, [&](const int r) {
return rmq.max(idx[v], r + 1) <= R[i];
});
ret[i] = right >= left;
}
}
return ret;
}
}
