#include "werewolf.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define pb push_back
const int N = 4e5 + 5, LOG = 19, SQ = 600;
struct krt {
vector<int> g[N];
int a[N], p[N], W[N], tin[N], tout[N], up[LOG][N], C, tm;
bool fl = 0; // fl = 1 za MX, 0 za MN
void init(int n) {
C = n-1;
iota(p, p+N, 0);
iota(W, W+N, 0);
}
int get(int x) {
if (x == p[x]) return x;
return p[x] = get(p[x]);
}
bool unite(int u, int v) {
u = get(u), v = get(v);
if (u == v) return 0;
p[u] = p[v] = ++C;
W[C] = (fl ? min(W[u], W[v]) : max(W[u], W[v]));
g[C].pb(u); g[C].pb(v); g[u].pb(C); g[v].pb(C);
return 1;
}
void dfs(int s, int e = -1) {
tin[s] = ++tm;
a[tm] = s;
for (auto u : g[s]) {
if (u == e) continue;
up[0][u] = s;
dfs(u, s);
}
tout[s] = tm;
}
void init2() {
dfs(C);
up[0][C] = C+1;
up[0][C+1] = C+1;
for (int i = 1; i < LOG; ++i) {
for (int j = 0; j <= C+1; ++j) up[i][j] = up[i-1][up[i-1][j]];
}
}
int F(int s, int l, int r) {
for (int i = LOG-1; i >= 0; --i) {
if (up[i][s] != C+1 && l <= W[up[i][s]] && W[up[i][s]] <= r) s = up[i][s];
}
return s;
}
} MN, MX;
struct bit {
int b[N];
void add(int p, int x) {
for (; p < N; p |= (p + 1)) b[p] += x;
}
int sum(int r) {
int S = 0;
for (; r >= 0; r = (r & (r + 1)) - 1) S += b[r];
return S;
}
int sum(int l, int r) {
return sum(r) - sum(l - 1);
}
} T;
bool cmp(array<int, 4> &A, array<int, 4> &B) {
if (A[0] / SQ != B[0] / SQ) return A[0] / SQ < B[0] / SQ;
return A[1] < B[1];
}
bool cmp1(array<int, 2> &A, array<int, 2> &B) {
return max(A[0], A[1]) < max(B[0], B[1]);
}
bool cmp2(array<int, 2> &A, array<int, 2> &B) {
return min(A[0], A[1]) > min(B[0], B[1]);
}
vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
MN.init(n); MX.init(n); MN.fl = 0, MX.fl = 1;
int q = S.size(), m = X.size();
array<int, 2> e[m];
for (int i = 0; i < m; ++i) e[i] = {X[i], Y[i]};
sort(e, e+m, cmp1);
for (int i = 0; i < m; ++i) MN.unite(e[i][0], e[i][1]);
sort(e, e+m, cmp2);
for (int i = 0; i < m; ++i) MX.unite(e[i][0], e[i][1]);
MX.init2(); MN.init2();
array<int, 4> qu[q];
for (int i = 0; i < q; ++i) {
int x = MX.F(S[i], L[i], n-1);
qu[i] = {MX.tin[x], MX.tout[x], E[i], i};
int y = MN.F(E[i], 0, R[i]);
// cout << MX.tin[x] << ' ' << MX.tout[x] << ' ' << MN.tin[y] << ' ' << MN.tout[y] << '\n';
}
// for (int i = 1; i <= MX.tm; ++i) cout << MX.a[i] << ' ';
// cout << '\n';
// for (int i = 1; i <= MN.tm; ++i) cout << MN.a[i] << ' ';
// cout << '\n';
sort(qu, qu + q, cmp);
int r = -1, l = 0;
vector<int> ans(q);
for (int i = 0; i < q; ++i) {
while (r > qu[i][1]) {
if (MX.a[r] < n) T.add(MN.tin[MX.a[r]], -1);
--r;
}
while (r < qu[i][1]) {
++r;
if (MX.a[r] < n) T.add(MN.tin[MX.a[r]], 1);
}
while (l > qu[i][0]) {
--l;
if (MX.a[l] < n) T.add(MN.tin[MX.a[l]], 1);
}
while (l < qu[i][0]) {
if (MX.a[l] < n) T.add(MN.tin[MX.a[l]], -1);
++l;
}
int x = MN.F(qu[i][2], 0, R[qu[i][3]]);
ans[qu[i][3]] = T.sum(MN.tin[x], MN.tout[x]) > 0;
}
return ans;
}
