#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
template<typename T>
struct SparseTable {
int len;
vector<vector<T>> st;
T (*F) (T, T);
void init(vector<T> &a, T (*f) (T, T)) {
F = f;
len = (int)a.size();
int mxpw = 32 - __builtin_clz(len);
st.resize(mxpw);
st[0] = a;
for(int k = 1; k < mxpw; k++) {
st[k].resize(len - (1 << k));
for(int i = 0; i < (int)st[k].size(); i++)
st[k][i] = F(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
}
}
T get(int l, int r) {
if(r > l || l < 0 || r >= len) {
cerr << "Wrong range in Sparse Table\n";
cerr << "size = " << len << '\n';
cerr << "range query: " << '[' << l << ", " << r << ']' << '\n';
exit(1);
}
int mxpw = 31 - __builtin_clz(r - l + 1);
return F(st[mxpw][l], st[mxpw][r - (1 << mxpw) + 1]);
}
};
int n, m, q;
const int N = 2e5 + 10;
vector<int> g[N];
vector<int> cnt;
vector<bool> us;
void dfs(int s, int l, int r) {
us[s] = 1;
cnt[s]++;
for(int to : g[s]) {
if(us[to] || to > r || to < l) continue;
dfs(to, l, r);
}
}
vector<int> order;
int tin[N];
void tour(int s, int p) {
tin[s] = (int)order.size();
order.push_back(s);
for(int to : g[s])
if(to != p)
tour(to, s);
}
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, m = (int)X.size(), q = (int)S.size();
vector<int> res(q);
for(int i = 0; i < m; i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
if(n <= 3000 && q <= 3000) {
for(int i = 0; i < q; i++) {
cnt.assign(n, 0);
us.assign(n, false);
dfs(S[i], L[i], n - 1);
us.assign(n, false);
dfs(E[i], 0, R[i]);
if(*max_element(cnt.begin(), cnt.end()) > 1)
res[i] = 1;
}
return res;
}
int root = 0;
while(root < n && g[root].size() > 1) root++;
tour(root, root);
SparseTable<int> mn, mx;
mn.init(order, [](int a, int b) {return (a > b ? b : a);});
mx.init(order, [](int a, int b) {return (a < b ? b : a);});
for(int i = 0; i < q; i++) {
int x = tin[S[i]], y = tin[E[i]], lb, rb;
int sl = x, sr = x, el = y, er = y;
lb = x, rb = n;
while(rb - lb > 1) {
int mid = (lb + rb) / 2;
if(mn.get(x, mid) >= L[i]) lb = mid;
else rb = mid;
}
sr = lb;
lb = 0, rb = x;
while(rb - lb > 1) {
int mid = (lb + rb) / 2;
if(mn.get(mid, x) >= L[i]) rb = mid;
else lb = mid;
}
sl = rb;
lb = y, rb = n;
while(rb - lb > 1) {
int mid = (lb + rb) / 2;
if(mx.get(y, mid) <= R[i]) lb = mid;
else rb = mid;
}
er = lb;
lb = 0, rb = y;
while(rb - lb > 1) {
int mid = (lb + rb) / 2;
if(mx.get(mid, y) <= R[i]) rb = mid;
else lb = mid;
}
el = rb;
int ll = max(sl, el), rr = min(sr, er);
res[i] = (ll <= rr);
}
return res;
}
