#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define mt make_tuple
using iii = tuple<int, int, int>;
int hpos, wpos, to[200005], link[200005], sz[200005], rep[200005], ancH[600005][25], ancW[600005][25], depH[600005], depW[600005], stH[600005], edH[600005], stW[600005], edW[600005];
vector<int> hadj[600005], wadj[600005];
iii human[400005], wolf[400005];
int find(int x) {
if (x == link[x]) return x;
return link[x] = find(link[x]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (sz[b] > sz[a]) swap(a, b);
sz[a] += sz[b];
link[b] = a;
}
void dfsH(int n, int e = -1) {
ancH[n][0] = e;
for (int i = 1; i <= 20; i++)
if (ancH[n][i - 1] != -1)
ancH[n][i] = ancH[ancH[n][i - 1]][i - 1];
int minst = 1e9, maxed = -1e9;
for (auto u : hadj[n])
if (u != e) {
depH[u] = depH[n] + 1;
dfsH(u, n);
minst = min(minst, stH[u]);
maxed = max(maxed, edH[u]);
}
stH[n] = minst;
edH[n] = maxed;
if (hadj[n].empty())
stH[n] = edH[n] = hpos++;
}
void dfsW(int n, int e = -1) {
ancW[n][0] = e;
for (int i = 1; i <= 20; i++)
if (ancW[n][i - 1] != -1)
ancW[n][i] = ancW[ancW[n][i - 1]][i - 1];
int minst = 1e9, maxed = -1e9;
for (auto u : wadj[n])
if (u != e) {
depW[u] = depW[n] + 1;
dfsW(u, n);
minst = min(minst, stW[u]);
maxed = max(maxed, edW[u]);
}
stW[n] = minst;
edW[n] = maxed;
if (wadj[n].empty())
stW[n] = edW[n] = wpos++;
}
struct node {
node *left, *right;
int S, E;
vector<int> val;
node(int _s, int _e) : S(_s), E(_e) {
if (S == E) {
val.pb(to[S]);
return;
}
int M = (S + E) >> 1;
left = new node(S, M);
right = new node(M + 1, E);
merge(left->val.begin(), left->val.end(), right->val.begin(), right->val.end(), back_inserter(val));
}
bool qry(int l, int r, int l2, int r2) {
if (l > E || r < S) return 0;
if (l <= S && E <= r) {
auto it = lower_bound(val.begin(), val.end(), l2);
if (it == val.end() || *it > r2) return 0;
return 1;
}
return left->qry(l, r, l2, r2) || right->qry(l, r, l2, r2);
}
} *root;
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
memset(ancH, -1, sizeof ancH);
memset(ancW, -1, sizeof ancW);
int M = X.size();
for (int i = 0; i < N; i++) {
link[i] = rep[i] = i;
sz[i] = 1;
}
for (int i = 0; i < M; i++) {
human[i] = mt(min(X[i], Y[i]), X[i], Y[i]);
wolf[i] = mt(max(X[i], Y[i]), X[i], Y[i]);
}
sort(human, human + X.size(), greater<iii>());
sort(wolf, wolf + X.size());
for (int i = 0; i < M; i++) {
auto [w, u, v] = human[i];
int a = rep[find(u)], b = rep[find(v)];
if (a != b) {
hadj[N + i].pb(a);
hadj[N + i].pb(b);
} else {
hadj[N + i].pb(a);
}
unite(u, v);
rep[find(u)] = N + i;
}
for (int i = 0; i < N; i++) {
link[i] = rep[i] = i;
sz[i] = 1;
}
for (int i = 0; i < M; i++) {
auto [w, u, v] = wolf[i];
int a = rep[find(u)], b = rep[find(v)];
if (a != b) {
wadj[N + i].pb(a);
wadj[N + i].pb(b);
} else {
wadj[N + i].pb(a);
}
unite(u, v);
rep[find(u)] = N + i;
}
dfsH(N + M - 1);
dfsW(N + M - 1);
for (int i = 0; i < N; i++)
to[stH[i]] = stW[i];
root = new node(0, N - 1);
int Q = S.size();
vector<int> A;
for (int i = 0; i < Q; i++) {
for (int j = 20; j >= 0; j--)
if (ancH[S[i]][j] != -1 && g0(human[ancH[S[i]][j] - N]) >= L[i]) S[i] = ancH[S[i]][j];
for (int j = 20; j >= 0; j--)
if (ancW[E[i]][j] != -1 && g0(wolf[ancW[E[i]][j] - N]) <= R[i]) E[i] = ancW[E[i]][j];
A.pb(root->qry(stH[S[i]], edH[S[i]], stW[E[i]], edW[E[i]]));
}
return A;
}
