#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;
}
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
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;
// If the first node in adjacency list is parent
// then need to choose the other one (index 1)
int next = (adj[u][0] == parent);
parent = u;
u = adj[u][next];
}
SparseTable<int,RMin<int>> st_min(order, RMin<int>());
SparseTable<int,RMax<int>> st_max(order, RMax<int>());
REP(i, Q) {
pair<int,int> s_int;
if (S[i] >= L[i] && E[i] <= R[i]) {
pair<int,int> s_int(find_left(st_min, st_max, pos[S[i]], L[i], N-1),
find_right(st_min, st_max, pos[S[i]], L[i], N-1, N));
pair<int,int> e_int(find_left(st_min, st_max, pos[E[i]], 0, R[i]),
find_right(st_min, st_max, pos[E[i]], 0, R[i], N));
A[i] = range_intersect(s_int, e_int);
}
}
} 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;
}
