#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
struct SegTree {
const static int N = (1 << 18);
vector<int> t;
SegTree() {
t.assign(2 * N, -1);
}
void update(int pos, int val) {
for(t[pos += N] = val; pos > 1; pos >>= 1) {
t[pos >> 1] = max(t[pos], t[(pos ^ 1)]);
}
}
int get(int ql, int qr) {
int res = -1;
for(ql += N, qr += N + 1; ql < qr; ql >>= 1, qr >>= 1) {
if(ql & 1) res = max(t[ql++], res);
if(qr & 1) res = max(t[--qr], res);
}
return res;
}
};
struct DSU {
vector<int> p, r;
DSU(int n) {
p.assign(n, 0);
r.assign(n, 1);
iota(p.begin(), p.end(), 0);
}
int find(int x) {
return p[x] = (p[x] == x ? x : find(p[x]));
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if(u == v) return;
p[v] = u;
}
};
const int N = 200010;
struct Tree {
vector<int> g[N];
vector<int> order;
int tin[N], tout[N], anc[N][18];
void dfs(int s, int p) {
tin[s] = (int)order.size();
order.push_back(s);
anc[s][0] = p;
for(int i = 1; i < 18; i++)
anc[s][i] = anc[anc[s][i - 1]][i - 1];
for(int to : g[s]) {
if(to == p) continue;
dfs(to, s);
}
tout[s] = (int)order.size() - 1;
}
};
Tree LL, RR;
vector<int> g[N];
SegTree st;
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> T,
vector<int> L, vector<int> R) {
int m = (int)X.size(), q = (int)S.size();
for(int i = 0; i < m; i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
DSU ds(N);
for(int i = 0; i < N; i++) {
for(int to : g[i]) {
to = ds.find(to);
if(to >= i) continue;
ds.merge(i, to);
RR.g[i].push_back(to);
}
}
ds = DSU(N);
for(int i = N - 1; i >= 0; i--) {
for(int to : g[i]) {
to = ds.find(to);
if(to <= i) continue;
ds.merge(i, to);
LL.g[i].push_back(to);
}
}
LL.dfs(0, 0);
RR.dfs(N - 1, N - 1);
vector<int> qr[N];
vector<int> res(q);
for(int i = 0; i < q; i++) {
for(int k = 17; k >= 0; k--) {
if(LL.anc[S[i]][k] >= L[i])
S[i] = LL.anc[S[i]][k];
if(RR.anc[T[i]][k] <= R[i])
T[i] = RR.anc[T[i]][k];
}
qr[LL.tout[S[i]]].push_back(i);
}
for(int i = 0; i < N; i++) {
int x = LL.order[i];
st.update(RR.tin[x], i);
for(int query : qr[i]) {
int l = RR.tin[T[query]], r = RR.tout[T[query]];
res[query] = (st.get(l, r) >= LL.tin[S[query]]);
}
}
return res;
}
