#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 1, LG = 19; //(int)log2(MAX_N);
int mx[LG][MAX_N], mn[LG][MAX_N];
int getMN(int l, int r)
{
int i = 0, p2 = 1;
while (p2 <= r - l + 1)
++i, p2 <<= 1;
--i, p2 >>= 1;
return min(mn[i][l], mn[i][r - p2 + 1]);
}
int getMX(int l, int r)
{
int i = 0, p2 = 1;
while (p2 <= r - l + 1)
++i, p2 <<= 1;
--i, p2 >>= 1;
return max(mx[i][l], mx[i][r - p2 + 1]);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
int M = X.size(), Q = S.size();
vector<int> A(Q);
if (N <= 3000 && M <= 6000 && Q <= 3000)
{
vector<vector<int>> g(N);
for (int i = 0; i < M; ++i)
{
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
for (int qq = 0; qq < Q; ++qq)
{
int s = S[qq], e = E[qq], l = L[qq], r = R[qq];
vector<bool> H(N);
queue<int> q;
q.push(s), H[s] = true;
while (!q.empty())
{
int x = q.front();
q.pop();
for (int y : g[x])
{
if (!H[y] && y >= l)
q.push(y), H[y] = true;
}
}
vector<bool> W(N);
q.push(e), W[e] = true;
while (!q.empty())
{
int x = q.front();
q.pop();
for (int y : g[x])
{
if (!W[y] && y <= r)
q.push(y), W[y] = true;
}
}
for (int i = 0; i < N; ++i)
{
if (H[i] && W[i] && l <= i && i <= r)
A[qq] = 1;
}
}
}
else
{
vector<vector<int>> g(N);
for (int i = 0; i < M; ++i)
{
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
int endPoint = 0;
for (int i = 0; i < N; ++i)
{
if (g[i].size() == 1)
{
endPoint = i;
break;
}
}
vector<int> id(N);
id[0] = endPoint;
for (int i = 1, cur = g[id[0]][0]; i < N; ++i)
{
id[i] = cur;
cur = g[cur][0] + g[cur][1] - id[i - 1];
}
vector<int> linePos(N);
for (int i = 0; i < N; ++i)
linePos[id[i]] = i;
for (int i = 0; i < N; ++i)
mx[0][i] = mn[0][i] = id[i];
for (int i = 1, p2 = 1; i < LG; ++i, p2 <<= 1)
{
for (int j = 0; j < N; ++j)
{
mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + p2]);
mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + p2]);
}
}
for (int qq = 0; qq < Q; ++qq)
{
int s = S[qq], e = E[qq], l = L[qq], r = R[qq];
s = linePos[s], e = linePos[e];
if (s < e)
{
int l = s - 1, r = e;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (getMX(mid, e) > r)
l = mid;
else
r = mid;
}
int lastH = l;
l = s, r = e + 1;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (getMN(s, mid) < l)
r = mid;
else
l = mid;
}
int firstW = r;
if (lastH + 1 < firstW)
A[qq] = 1;
}
else
{
int l = e - 1, r = s;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (getMN(mid, s) < l)
l = mid;
else
r = mid;
}
int lastW = l;
l = e, r = s + 1;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (getMX(e, mid) > r)
r = mid;
else
l = mid;
}
int firstH = r;
if (lastW + 1 < firstH)
A[qq] = 1;
}
}
}
return A;
}
