#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
template<typename T> class fenwick_t {
public:
vector<T> fenw;
int n;
fenwick_t(int n):n(n) {
fenw.resize(n);
}
void modify(int x, T value) {
while (x < n) {
fenw[x] += value;
x |= x + 1;
}
}
T query(int x) {
T result{};
while (x >= 0) {
result += fenw[x];
x = (x & x + 1) - 1;
}
return result;
}
};
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
int m = x.size(), q = s.size();
struct tree_t {
struct edge_t {
int u, v, w;
edge_t(int u = 0, int v = 0, int w = 0):u(u), v(v), w(w) {
}
bool operator < (const edge_t &b) const {
return w < b.w;
}
};
vector<int> l, r, left, right, value;
vector<vector<int>> ancestor;
int n, log_n, total, counter;
vector<edge_t> edge;
tree_t(int n):n(n) {
l = r = left = right = value = vector<int> ((n << 1) - 1, -1);
total = n;
log_n = counter = 0;
while (1 << log_n <= n) {
++log_n;
}
ancestor = vector<vector<int>> (log_n, vector<int> ((n << 1) - 1, -1));
}
void dfs(int x) {
left[x] = counter++;
if (x >= n) {
dfs(l[x]);
dfs(r[x]);
}
right[x] = counter;
}
void init() {
sort(edge.begin(), edge.end());
vector<int> p((n << 1) - 1);
for (int i = 0; i < (n << 1) - 1; ++i) {
p[i] = i;
}
function<int(int)> find = [&](int x) {
while (x != p[x]) {
x = p[x] = p[p[x]];
}
return x;
};
total = n;
for (auto e : edge) {
if (find(e.u) != find(e.v)) {
l[total] = find(e.u);
r[total] = find(e.v);
ancestor[0][find(e.u)] = ancestor[0][find(e.v)] = total;
value[total] = e.w;
p[find(e.u)] = p[find(e.v)] = total;
total++;
}
}
for (int i = 1; i < log_n; ++i) {
for (int j = 0; j < (n << 1) - 1; ++j) {
if (~ancestor[i - 1][j]) {
ancestor[i][j] = ancestor[i - 1][ancestor[i - 1][j]];
}
}
}
dfs(n - 1 << 1);
}
int go(int x, int limit) {
for (int i = log_n - 1; ~i; --i) {
if (~ancestor[i][x] && value[ancestor[i][x]] <= limit) {
x = ancestor[i][x];
}
}
return x;
}
};
tree_t prefix(n), suffix(n);
for (int i = 0; i < m; ++i) {
prefix.edge.emplace_back(x[i], y[i], max(x[i], y[i]));
suffix.edge.emplace_back(x[i], y[i], -min(x[i], y[i]));
}
prefix.init();
suffix.init();
vector<pair<int, int>> points;
fenwick_t<int> fenwick((n << 1) - 1);
for (int i = 0; i < n; ++i) {
points.emplace_back(prefix.left[i], suffix.left[i]);
}
sort(points.begin(), points.end());
struct event_t {
int x, l, r, id, sign;
event_t(int x = 0, int l = 0, int r = 0, int id = 0, int sign = 0):x(x), l(l), r(r), id(id), sign(sign) {
}
bool operator < (const event_t &b) const {
return x < b.x;
}
};
vector<event_t> events;
vector<int> answer(q);
for (int i = 0; i < q; ++i) {
int x = prefix.go(e[i], r[i]), y = suffix.go(s[i], -l[i]);
events.emplace_back(prefix.left[x], suffix.left[y], suffix.right[y], i, -1);
events.emplace_back(prefix.right[x], suffix.left[y], suffix.right[y], i, 1);
}
sort(events.begin(), events.end());
int current = 0;
for (auto event : events) {
while (current < n && points[current].first < event.x) {
fenwick.modify(points[current++].second, 1);
}
answer[event.id] += event.sign * (fenwick.query(event.r - 1) - fenwick.query(event.l - 1));
}
for (int i = 0; i < q; ++i) {
if (answer[i]) {
answer[i] = 1;
}
}
return answer;
}
