#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); i++)
template<typename T>
struct RMin {
T operator()(const T& a, const T& b) {
if (a < b) return a;
return b;
}
};
template<typename T>
struct RMax {
T operator()(const T& a, const T& b) {
if (a > b) return a;
return b;
}
};
// Op: Aggregation (min/max/sum/gcd)
// T: Underlying type
// For non idempotent aggregation (e.g. sum), need query_log,
// else query_const
template<typename T, typename Op>
class SparseTable {
private:
Op m_op;
vector<vector<T>> m_table;
size_t m_n;
size_t m_log;
void build(const vector<T>& data) {
copy(data.begin(), data.end(), m_table[0].begin());
for (int i = 1; i <= m_log; ++i) {
for (int j = 0; j + (1 << i) <= m_n; ++j) {
m_table[i][j] = m_op(m_table[i-1][j], m_table[i-1][j + (1 << (i-1))]);
}
}
}
int log2_floor(unsigned long i) {
return i ? 63 - __builtin_clzll(i) : -1;
}
public:
SparseTable(vector<T>& data, Op op) : m_n{data.size()}, m_log{0}, m_op{op} {
while ((1 << (m_log+1)) <= m_n) {
++m_log;
}
m_table.resize(m_log + 1, vector<T>(m_n));
build(data);
}
T query_const(int l, int r) {
int i = log2_floor(r - l + 1);
return m_op(m_table[i][l],
m_table[i][r - (1 << i) + 1]);
}
T query_log(int l, int r) {
T res{};
for (int i = m_log; i >= 0; --i) {
if ((1 << i) <= r - l + 1) {
res = m_op(res, m_table[i][l]);
l += 1 << i;
}
}
return res;
}
};
// Two ranges [l0, r0]
// [l1, r1]
// Intersect if there is x s.t. l0 <= x <= r0 and l1 <= x <= r1
// Assuming l1 <= r1 and l0 <= r0
// l0 <= r1 && l1 <= r0
bool range_intersect(const pair<int,int>& a, const pair<int,int>& b) {
return a.first <= b.second && b.first <= a.second;
}
vector<bool> reachable(vector<vector<int>>& adjList, int start, int lo, int hi) {
const int N = adjList.size();
vector<bool> vis(N, false);
queue<int> q;
if (start >= lo && start <= hi) {
q.push(start);
vis[start] = true;
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto& v : adjList[u]) {
if (lo <= v && v <= hi && !vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
return vis;
}
// Invariant: Interval [up,x] valid
int find_left(SparseTable<int, RMin<int>>& st_min,
SparseTable<int, RMax<int>>& st_max, int x, int l, int r) {
int lb = 0;
int up = x;
while (lb != up) {
int s = (lb + up) / 2;
int mn = st_min.query_const(s, x);
int mx = st_max.query_const(s, x);
if (mn >= l && mx <= r) {
up = s;
} else {
lb = s+1;
}
}
return up;
}
// Invariant: Interval [x,lb] valid
int find_right(SparseTable<int, RMin<int>>& st_min,
SparseTable<int, RMax<int>>& st_max, int x, int l, int r, int N) {
int lb = x;
int up = N-1;
while (lb != up) {
int s = (lb + up + 1) / 2;
int mn = st_min.query_const(x, s);
int mx = st_max.query_const(x, s);
if (mn >= l && mx <= r) {
lb = s;
} else {
up = s-1;
}
}
return lb;
}
int fufind(vector<int>& fu, int x) {
if (fu[x] < 0) {return x;} // x is root
fu[x] = fufind(fu, fu[x]);
return fu[x];
}
void fujoin(vector<int>& fu, vector<int>& pos_sml, vector<int>& pos_big, int x, int y) {
x = fufind(fu, x);
y = fufind(fu, y);
if (x != y) {
fu[y] = x;
pos_sml[x] = min(pos_sml[x], pos_sml[y]);
pos_big[x] = max(pos_big[x], pos_big[y]);
}
}
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 Q = S.size();
int M = X.size();
vector<int> A(Q);
vector<vector<int> > adj(N);
REP(i, M) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
// Check for line graph
bool isLine = true;
REP(i, N) {
isLine = isLine && (adj[i].size() <= 2);
}
// Subtask 3: Line graph
// DSU solution
if (isLine) {
// Linearize graph
int u = -1;
int parent = -1;
REP(i, N) {
if (adj[i].size() == 1) {u = i; break;}
}
vector<int> order(N);
vector<int> pos(N);
REP(i, N) {
order[i] = u;
pos[u] = i;
int next = (adj[u][0] == parent);
parent = u;
u = adj[u][next];
}
// Idea: Define V_L as set of vertices reachable from S
// that have values in range [L,N-1]
// They form an interval surrounding S
vector<int> fu(N);
vector<int> pos_sml(N);
vector<int> pos_big(N);
vector<pair<int,int>> Lrange(Q);
vector<pair<int,int>> Rrange(Q);
// Sort queries by L[i] (non-increasing)
vector<int> idx(Q);
REP(i, Q) {idx[i] = i;}
sort(idx.begin(), idx.end(), [&](int i0, int i1) {
return L[i0] > L[i1];
});
// Initialize DSU structure
REP(i, N) {
fu[i] = -1;
pos_sml[i] = pos_big[i] = pos[i];
}
// Calculate V_L
int next = N-1;
REP(i, Q) {
int limit = L[idx[i]];
for (; next >= limit; --next) {
for (int u : adj[next]) {
if (u >= limit) {
fujoin(fu, pos_sml, pos_big, next, u);
}
}
}
int lead = fufind(fu, S[idx[i]]);
Lrange[idx[i]] = make_pair(pos_sml[lead], pos_big[lead]);
}
// Calculate V_R
REP(i, Q) {idx[i] = i;}
vector<int> idx1(Q);
REP(i, Q) {idx1[i] = i;}
sort(idx1.begin(), idx1.end(), [&](int i0, int i1) {
return R[i0] < R[i1];
});
REP(i, N) {
fu[i] = -1;
pos_sml[i] = pos_big[i] = pos[i];
}
next = 0;
REP(i, Q) {
int limit = R[idx1[i]];
for(; next <= limit; ++next) {
for (int u : adj[next]) {
if (u <= limit) {
fujoin(fu, pos_sml, pos_big, next, u);
}
}
}
int lead = fufind(fu, E[idx1[i]]);
Rrange[idx1[i]] = make_pair(pos_sml[lead], pos_big[lead]);
}
REP(i,Q) {
A[i] = range_intersect(Lrange[i], Rrange[i]);
}
} else {
REP(i, Q) {
vector<bool> reach_S = reachable(adj, S[i], L[i], N-1);
vector<bool> reach_E = reachable(adj, E[i], 0, R[i]);
REP(v, N) {
A[i] |= reach_S[v] && reach_E[v];
if (A[i]) {break;}
}
}
}
return A;
}
