#include "werewolf.h"
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
ll n;
struct MST{
vector <ll> adj[200000];
array <ll, 2> R[200000];
ll P[200000], bl[200000][18], dfn[200000], ord[200000], cur = -1;
ll dsu(ll u) {
if (P[u] == u) return u;
else return P[u] = dsu(P[u]);
}
void construct_lift() {
for (int k=1; k<18; ++k) {
for (int i=0; i<n; ++i) {
bl[i][k] = bl[bl[i][k-1]][k-1];
}
}
}
ll find_ancestor(ll u, ll x) {
for (int k=17; k>=0; --k) {
if (u != x && (bl[u][k] == x || !((u < x) ^ (bl[u][k] < x)))) {
u = bl[u][k];
}
}
return u;
}
void dfs(ll u) {
R[u][0] = ++cur;
ord[cur] = u;
dfn[u] = cur;
for (auto v : adj[u]) {
dfs(v);
}
R[u][1] = cur;
}
}MN, MX;
struct SegTree{
vector <ll> st[800000];
void build(ll id, ll l, ll r) {
st[id].resize(r-l+1);
ll sz = 0;
if (l == r) {
st[id][sz++] = MN.dfn[MX.ord[l]];
return;
}
ll mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
int i = 0, j = 0;
while (i < st[id*2].size() && j < st[id*2+1].size()) {
if (st[id*2][i] <= st[id*2+1][j]) st[id][sz++] = st[id*2][i++];
else st[id][sz++] = st[id*2+1][j++];
}
while (i < st[id*2].size()) st[id][sz++] = st[id*2][i++];
while (j < st[id*2+1].size()) st[id][sz++] = st[id*2+1][j++];
}
bool query(ll id, ll l, ll r, ll ql, ll qr, ll qx, ll qy) {
if (qr < l || r < ql) return 0;
else if (ql <= l && r <= qr) {
auto it = lower_bound(st[id].begin(), st[id].end(), qx);
if (it != st[id].end() && *it <= qy) return 1;
else return 0;
}
ll mid = (l+r)/2;
return query(id*2, l, mid, ql, qr, qx, qy) | query(id*2+1, mid+1, r, ql, qr, qx, qy);
}
}ST;
vector <array<ll, 2>> edge;
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
n = N;
for (int i=0; i<N; ++i) {
MN.P[i] = MX.P[i] = MN.bl[i][0] = MX.bl[i][0] = i;
}
for (int i=0; i<X.size(); ++i) {
edge.push_back({X[i], Y[i]});
}
sort(edge.begin(), edge.end(), [](auto a, auto b) {
return max(a[0], a[1]) < max(b[0], b[1]);
});
for (auto [u, v] : edge) {
auto a = MN.dsu(u), b = MN.dsu(v);
if (a != b) {
if (a > b) swap(a, b);
MN.P[a] = b;
MN.adj[b].push_back(a);
MN.bl[a][0] = b;
}
}
MN.construct_lift();
MN.dfs(n-1);
sort(edge.begin(), edge.end(), [](auto a, auto b) {
return min(a[0], a[1]) > min(b[0], b[1]);
});
for (auto [u, v] : edge) {
auto a = MX.dsu(u), b = MX.dsu(v);
if (a != b) {
if (a < b) swap(a, b);
MX.P[a] = b;
MX.adj[b].push_back(a);
MX.bl[a][0] = b;
}
}
MX.construct_lift();
MX.dfs(0);
ST.build(1, 0, n-1);
vector <int> Q;
for (int i=0; i<S.size(); ++i) {
auto a = MX.find_ancestor(S[i], L[i]);
auto b = MN.find_ancestor(E[i], R[i]);
Q.push_back(ST.query(1, 0, n-1, MX.R[a][0], MX.R[a][1], MN.R[b][0], MN.R[b][1]));
}
return Q;
}
