#include "werewolf.h"
#include <algorithm>
using namespace std;
typedef long long llong;
int n, m, q;
vector<int> edge[200000];
struct UF {
int par[200000];
UF() {
for (int i = 0; i < 200000; ++i) par[i] = i;
}
int find(int x) {
if (par[x] != x) return par[x] = find(par[x]);
return x;
}
} Luf, Ruf;
int Lpar[200000][20];
int Rpar[200000][20];
vector<int> Lchild[200000];
vector<int> Rchild[200000];
int Lst[200000];
int Led[200000];
int Rst[200000];
int Red[200000];
int LRd[200000];
void dfs(vector<int> child[], int st[], int ed[], int x, int &d) {
st[x] = ++d;
for (int i : child[x]) {
dfs(child, st, ed, i, d);
}
ed[x] = d;
}
struct query {
int i, t, x;
query(int i, int t, int x) : i(i), t(t), x(x) {}
bool operator<(const query &p) const {
return t < p.t;
}
};
int seg[200001];
void update(int i) {
while (i <= n) {
++seg[i];
i += i & -i;
}
}
int sum(int i) {
int ret = 0;
while (i) {
ret += seg[i];
i -= i & -i;
}
return ret;
}
vector<int> check_validity(int N, vector<int> U, vector<int> V
, vector<int> X, vector<int> Y, vector<int> L, vector<int> R) {
n = N;
m = U.size();
q = X.size();
for (int i = 0; i < m; ++i) {
edge[U[i]].push_back(V[i]);
edge[V[i]].push_back(U[i]);
}
for (int i = 0; i < n; ++i) Lpar[i][0] = 0;
for (int i = n; i--; ) {
for (int j : edge[i]) {
if (j < i) continue;
int x = Luf.find(i);
int y = Luf.find(j);
if (x == y) continue;
Luf.par[y] = x;
Lpar[y][0] = x;
Lchild[x].push_back(y);
}
}
for (int i = 0; i < n; ++i) Rpar[i][0] = n - 1;
for (int i = 0; i < n; ++i) {
for (int j : edge[i]) {
if (i < j) continue;
int x = Ruf.find(i);
int y = Ruf.find(j);
if (x == y) continue;
Ruf.par[y] = x;
Rpar[y][0] = x;
Rchild[x].push_back(y);
}
}
for (int i = 1; i < 20; ++i) {
for (int j = 0; j < n; ++j) {
Lpar[j][i] = Lpar[Lpar[j][i - 1]][i - 1];
Rpar[j][i] = Rpar[Rpar[j][i - 1]][i - 1];
}
}
int ord;
ord = 0;
dfs(Lchild, Lst, Led, Luf.find(0), ord);
ord = 0;
dfs(Rchild, Rst, Red, Ruf.find(0), ord);
for (int i = 0; i < n; ++i) LRd[Lst[i] - 1] = Rst[i];
vector<query> qs;
for (int it = 0; it < q; ++it) {
int x = X[it];
int y = Y[it];
int l = L[it];
int r = R[it];
for (int i = 20; i--; ) if (l <= Lpar[x][i]) x = Lpar[x][i];
for (int i = 20; i--; ) if (Rpar[y][i] <= r) y = Rpar[y][i];
qs.emplace_back(~it, Lst[x] - 1, y);
qs.emplace_back(it, Led[x], y);
}
sort(qs.begin(), qs.end());
vector<int> ret(q, 0);
ord = 0;
for (query i : qs) {
while (ord < i.t) update(LRd[ord++]);
int v = sum(Red[i.x]) - sum(Rst[i.x] - 1);
if (i.i < 0) ret[~i.i] -= v;
else ret[i.i] += v;
}
for (int &i : ret) i = (i > 0);
return ret;
}
