#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int MAX_N = 2e5 + 5;
int N, M, Q;
vector <int> graph[MAX_N];
bool visited[MAX_N][2];
vector <int> order;
int enpos[MAX_N];
int tmax[MAX_N][20], tmin[MAX_N][20];
int getMin(int l, int r) {
int j = log2(r - l + 1);
return min(tmin[l][j], tmin[r - (1<<j) + 1][j]);
}
int getMax(int l, int r) {
int j = log2(r - l + 1);
return max(tmax[l][j], tmax[r - (1<<j) + 1][j]);
}
void dfs(int u, int p) {
order.push_back(u);
for(auto v : graph[u]) {
if(v != p) {
dfs(v, u);
}
}
}
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();
vector <int> answer(Q, 0);
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) {
for(int qq = 0; qq < Q; qq++) {
int s = S[qq], e = E[qq], l = L[qq], r = R[qq];
for(int i = 0; i < N; i++) {
visited[i][0] = false;
visited[i][1] = false;
}
queue <pair <int, int>> q;
if(s >= l) {
q.emplace(s, 0);
visited[s][0] = true;
}
while(!q.empty()) {
auto [u, k] = q.front();
q.pop();
if(k == 0 and l <= u and u <= r and visited[u][1] == false) {
visited[u][1] = true;
q.emplace(u, 1);
}
for(auto v : graph[u]) {
if(k == 0) {
if(v >= l and visited[v][0] == false) {
visited[v][0] = true;
q.emplace(v, 0);
}
}
else {
if(v <= r and visited[v][1] == false) {
visited[v][1] = true;
q.emplace(v, 1);
}
}
}
}
answer[qq] = visited[e][1];
}
}
else {
for(int i = 0; i < N; i++) {
if(graph[i].size() == 1) {
dfs(i, -1);
break;
}
}
for(int i = 0; i < N; i++) {
enpos[order[i]] = i;
tmin[i][0] = order[i];
tmax[i][0] = order[i];
}
for(int j = 1; j < 20; j++) {
for(int i = 0; i + (1<<j) - 1 < N; i++) {
tmin[i][j] = min(tmin[i][j - 1], tmin[i + (1<<(j - 1))][j - 1]);
tmax[i][j] = max(tmax[i][j - 1], tmax[i + (1<<(j - 1))][j - 1]);
}
}
for(int qq = 0; qq < Q; qq++) {
int s = S[qq], e = E[qq], ll = L[qq], rr = R[qq];
int l, r, mid, changeL, changeR;
if(enpos[order[s]] < enpos[order[e]]) {
l = enpos[order[s]], r = enpos[order[e]];
while(l <= r) {
mid = (l + r) / 2;
if(getMin(enpos[order[s]], mid) >= ll) {
l = mid + 1;
changeL = mid;
}
else {
r = mid - 1;
}
}
l = enpos[order[s]], r = enpos[order[e]];
while(l <= r) {
mid = (l + r) / 2;
if(getMax(mid, enpos[order[e]]) <= rr) {
r = mid - 1;
changeR = mid;
}
else {
l = mid + 1;
}
}
if(changeL >= changeR) {
answer[qq] = 1;
}
}
else {
l = enpos[order[e]], r = enpos[order[s]];
while(l <= r) {
mid = (l + r) / 2;
if(getMin(mid, enpos[order[s]]) >= ll) {
r = mid - 1;
changeL = mid;
}
else {
l = mid + 1;
}
}
l = enpos[order[e]], r = enpos[order[s]];
while(l <= r) {
mid = (l + r) / 2;
if(getMax(enpos[order[e]], mid) <= rr) {
l = mid + 1;
changeR = mid;
}
else {
r = mid - 1;
}
}
if(changeL <= changeR) {
answer[qq] = 1;
}
}
}
}
return answer;
}
