#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for(int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const int SIZE = 2e5 + 5;
const int H = __lg(SIZE);
int n, m, q;
vector<int> ans, adj[SIZE];
vector<pair<int, int>> ask[SIZE];
struct DSU {
int to[SIZE];
DSU() = default;
void init() {
iota(to, to + n, 0);
}
int dsu(int x) {
return x == to[x] ? x : (to[x] = dsu(to[x]));
}
};
struct Tree {
vector<int> adj[SIZE];
int root, to[SIZE][H + 1], h[SIZE];
int dfsid, in[SIZE], out[SIZE], w[SIZE];
DSU dsu;
Tree() = default;
void init() {
dfsid = -1;
dsu.init();
}
void add(int a, int b) {
a = dsu.dsu(a), b = dsu.dsu(b);
if (a == b) return;
adj[a].pb(b);
dsu.to[b] = a;
root = a;
}
void build() {
auto dfs = [&](auto dfs, int pos)->void {
in[pos] = ++dfsid;
w[pos] = 1;
for (int np : adj[pos]) {
h[np] = h[pos] + 1;
to[np][0] = pos;
dfs(dfs, np);
w[pos] += w[np];
}
out[pos] = dfsid;
};
to[root][0] = root;
dfs(dfs, root);
FOR (j, 1, H) FOR (i, 0, n - 1) to[i][j] = to[to[i][j - 1]][j - 1];
}
int sch(int pos, int lim, int ty) {
for (int i = H; i >= 0; i--) if ((ty == 1 && to[pos][i] >= lim) || (ty == 2 && to[pos][i] <= lim)) pos = to[pos][i];
return pos;
}
} t1, t2;
int a[SIZE], bit[SIZE];
void upd(int pos, int x) {
for (pos++; pos <= n; pos += pos & -pos) bit[pos] += x;
}
int que(int pos) {
int re = 0;
for (pos++; pos; pos -= pos & -pos) re += bit[pos];
return re;
}
int que(int l, int r) {
return que(r) - que(l - 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) {
n = N, m = X.size(), q = S.size();
ans.resize(q);
FOR (i, 0, m - 1) {
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
t1.init(), t2.init();
for (int i = n - 1; i >= 0; i--) for (int j : adj[i]) if (i < j) t1.add(i, j);
FOR (i, 0, n - 1) for (int j : adj[i]) if (i > j) t2.add(i, j);
t1.build(), t2.build();
FOR (i, 0, n - 1) a[t1.in[i]] = i;
FOR (i, 0, q - 1) {
S[i] = t1.sch(S[i], L[i], 1);
E[i] = t2.sch(E[i], R[i], 2);
ask[t1.out[S[i]]].pb(i, 1);
if (t1.in[S[i]]) ask[t1.in[S[i]] - 1].pb(i, -1);
}
FOR (i, 0, n - 1) {
upd(t2.in[a[i]], 1);
for (auto [id, coef] : ask[i]) ans[id] += coef * que(t2.in[E[id]], t2.out[E[id]]);
}
FOR (i, 0, q - 1) ans[i] = ans[i] > 0;
return ans;
}
