#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 2e5 + 100;
vector<int> g[mxn], a(mxn), id(mxn);
struct Node {
int mx = -1, mn = mxn;
Node operator + (Node a) {
return {max(mx, a.mx), min(mn, a.mn)};
}
} null;
struct SGT {
vector<Node> sgt;
SGT(int sz) {
sgt.resize(sz * 4);
}
void build(int k, int l, int r) {
if (l == r) {
sgt[k] = {a[l], a[l]};
return;
}
int mid = (l + r) / 2;
build(k * 2, l, mid);
build(k * 2 + 1, mid + 1, r);
sgt[k] = sgt[k * 2] + sgt[k * 2 + 1];
}
Node get(int k, int l, int r, int i, int j) {
if (l > j || r < i) return null;
if (i <= l && r <= j) return sgt[k];
int mid = (l + r) / 2;
return get(k * 2, l, mid, i, j) + get(k * 2 + 1, mid + 1, r, i, j);
}
} sgt(mxn);
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();
int Q = S.size();
vector<int> A(Q);
for (int i = 0; i < M; i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
int start = 0;
for (int i = 0; i < N; i++) if (g[i].size() == 1) start = i;
bool visited[N + 2];
memset(visited, 0, sizeof(visited));
int cnt = 0;
while (!visited[start]) {
visited[start] = 1;
id[start] = cnt;
a[cnt++] = start;
for (auto x : g[start]) {
if (!visited[x]) {
start = x;
break;
}
}
}
sgt.build(1, 0, N - 1);
for (int i = 0; i < Q; i++) {
if (id[S[i]] > id[E[i]]) swap(S[i], E[i]);
int mxL, mnR;
int l = id[S[i]], r = N;
while (l + 1 < r) {
int mid = (l + r) / 2;
Node get = sgt.get(1, 0, N - 1, l, mid);
if (get.mn >= L[i]) l = mid;
else r = mid;
}
mxL = l;
l = -1, r = id[E[i]];
while (l + 1 < r) {
int mid = (l + r) / 2;
Node get = sgt.get(1, 0, N - 1, mid, r);
if (get.mx <= R[i]) r = mid;
else l = mid;
}
mnR = r;
A[i] = (mxL >= mnR);
}
return A;
}
