#include "werewolf.h"
#include "bits/stdc++.h"
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vp = vector<P>;
using vvp = vector<vp>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;
template<class T>
bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
} else {
return false;
}
}
template<class T>
bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
} else {
return false;
}
}
class unionfind {
int n;
vi p;
public:
unionfind(int n) : n(n), p(n, -1) {}
int root(int x) {
if (p[x] < 0) return x;
return p[x] = root(p[x]);
}
bool same(int x, int y) { return root(x) == root(y); }
bool merge(int x, int y) {
x = root(x), y = root(y);
if (x == y) return false;
if (p[x] > p[y]) swap(x, y);
p[x] += p[y];
p[y] = x;
return true;
}
};
class BIT {
int n;
vi d;
int sum(int p) {
++p;
int res = 0;
for (; p >= 1; p -= p & -p) {
res += d[p];
}
return res;
}
public:
BIT(int n) : n(n), d(n + 1) {}
void add(int p, int x = 1) {
assert(0 <= p and p < n);
++p;
for (; p <= n; p += p & -p) {
d[p] += x;
}
}
int sum(int l, int r) {
assert(0 <= l and l <= r and r <= n);
return sum(r - 1) - sum(l - 1);
}
};
vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
int m = SZ(x), q = SZ(s);
vvi ord(2, vi(n));
vvi ql(2, vi(q));
vvi qr(2, vi(q));
rep(i, 2) {
vp es;
rep(j, m) {
if (x[j] > y[j]) swap(x[j], y[j]);
if (!i) es.eb(x[j], y[j]);
else es.eb(y[j], x[j]);
}
if (!i) sort(rall(es));
else sort(all(es));
unionfind uf(n);
vi rt(n);
iota(all(rt), 0);
vvi G(n);
for (auto[u, v]: es) {
if (uf.same(u, v)) continue;
v = rt[uf.root(v)];
G[u].pb(v);
G[v].pb(u);
uf.merge(u, v);
rt[uf.root(u)] = u;
}
vvi par(20, vi(n, -1));
vi in(n), out(n);
int iter = 0;
auto dfs = [&](auto &dfs, int u, int p) -> void {
par[0][u] = p;
ord[i][u] = in[u] = iter++;
for (int v: G[u]) {
if (v == p) continue;
dfs(dfs, v, u);
}
out[u] = iter;
};
dfs(dfs, (!i ? 0 : n - 1), -1);
rep(k, 19) rep(j, n) {
if (par[k][j] == -1) continue;
par[k + 1][j] = par[k][par[k][j]];
}
rep(j, q) {
int now = (!i ? s[j] : e[j]);
rrep(k, 20) {
if (par[k][now] == -1) continue;
if (!i and par[k][now] < l[j]) continue;
if (i and par[k][now] > r[j]) continue;
now = par[k][now];
}
// cerr << now << endl;
ql[i][j] = in[now];
qr[i][j] = out[now];
}
// rep(j, n) cerr << j << ' ' << in[j] << ' ' << out[j] << endl;
// rep(k, 20) rep(j, n) cerr << par[k][j] << (j == n - 1 ? '\n' : ' ');
}
vector<vector<tuple<int, int, int>>> qs(n + 1);
rep(i, q) {
int xl = ql[0][i];
int xr = qr[0][i];
int yl = ql[1][i];
int yr = qr[1][i];
// cerr << xl << ' ' << xr << ' ' << yl << ' ' << yr << endl;
qs[xl].eb(yl, yr, -(i + 1));
qs[xr].eb(yl, yr, i);
}
vi ans(q);
vp pt;
rep(i, n) pt.eb(ord[0][i], ord[1][i]);
sort(all(pt));
BIT bt(n);
for (auto[i, j]: pt) {
bt.add(j);
for (auto[yl, yr, t]: qs[i + 1]) {
if (t < 0) ans[-(t + 1)] -= bt.sum(yl, yr);
else ans[t] += bt.sum(yl, yr);
}
}
rep(i, q) chmin(ans[i], 1);
return ans;
}
