#include <bits/stdc++.h>
#include "werewolf.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 2;
const int mod = 1e9 + 7;
vector<int> g[2][N];
int in[2][N], out[2][N], tsz;
void Dfs(int s, int o) {
in[o][s] = ++tsz;
for (int u : g[o][s]) Dfs(u, o);
out[o][s] = tsz;
}
int st[4 * N];
void Add(int node, int l, int r, int p) {
st[node]++;
if (l == r) return;
int mid = l + r >> 1;
if (p <= mid) Add(2 * node, l, mid, p);
else Add(2 * node + 1, mid + 1, r, p);
}
int Get(int node, int l, int r, int ql, int qr) {
if (r < ql || qr < l) return 0;
if (ql <= l && r <= qr) return st[node];
int mid = l + r >> 1;
return Get(2 * node, l, mid, ql, qr) + Get(2 * node + 1, mid + 1, r, ql, qr);
}
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(); int q = s.size();
vector<int> link(n);
iota(link.begin(), link.end(), 0);
function<int(int)> Find = [&] (int x) {
if (x == link[x]) return x;
return link[x] = Find(link[x]);
};
function<void(int, int, int)> Unite = [&] (int x, int y, int o) {
x = Find(x);
y = Find(y);
if (x == y) return;
if (o == 0) {
link[max(x, y)] = min(x, y);
g[o][min(x, y)].push_back(max(x, y));
}
else {
link[min(x, y)] = max(x, y);
g[o][max(x, y)].push_back(min(x, y));
}
};
vector<array<int, 3>> all;
for (int i = 0; i < m; i++) all.push_back({min(x[i], y[i]), 0, i});
for (int i = 0; i < q; i++) all.push_back({l[i], 1, i});
sort(all.begin(), all.end(), [&] (array<int, 3> i, array<int, 3> j) {
if (i[0] != j[0]) return i[0] > j[0];
return i[1] < j[1];
});
vector<int> who1(q);
for (auto i : all) {
if (i[1] == 0) Unite(x[i[2]], y[i[2]], 0);
else who1[i[2]] = Find(s[i[2]]);
}
tsz = -1;
Dfs(0, 0);
iota(link.begin(), link.end(), 0);
all.clear();
for (int i = 0; i < m; i++) all.push_back({max(x[i], y[i]), 0, i});
for (int i = 0; i < q; i++) all.push_back({r[i], 1, i});
sort(all.begin(), all.end());
vector<int> who2(q);
for (auto i : all) {
if (i[1] == 0) Unite(x[i[2]], y[i[2]], 1);
else who2[i[2]] = Find(e[i[2]]);
}
tsz = -1;
Dfs(n - 1, 1);
vector<int> nz(n);
for (int i = 0; i < n; i++) nz[in[0][i]] = i;
vector<int> ans(q);
vector<vector<array<int, 4>>> qq(n);
for (int i = 0; i < q; i++) {
if (in[0][who1[i]] > 0) qq[in[0][who1[i]] - 1].push_back({i, -1, in[1][who2[i]], out[1][who2[i]]});
qq[out[0][who1[i]]].push_back({i, 1, in[1][who2[i]], out[1][who2[i]]});
}
for (int i = 0; i < n; i++) {
Add(1, 0, n - 1, in[1][nz[i]]);
for (auto j : qq[i]) {
ans[j[0]] += j[1] * Get(1, 0, n - 1, j[2], j[3]);
}
}
for (int i = 0; i < q; i++) smin(ans[i], 1);
return ans;
}
