#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define rb(x) ((x)&(-(x)))
const int MAXN = 200010;
int N;
int u[MAXN], d[MAXN];
int dot[MAXN];
vector<int> qry[MAXN];
vector<int> ed[MAXN];
int bit[MAXN];
struct TREE {
int par[20][MAXN], uni[MAXN];
vector<int> chi[MAXN];
int dfn[MAXN], dfr[MAXN];
int dfs(int x, int d) {
dfn[x] = dfr[x] = d;
for(auto a : chi[x]) dfr[x] = dfs(a, dfr[x] + 1);
return dfr[x];
}
int cnttt = 0;
int guni(int x) {
//if(++cnttt < 100) printf("uni[%d] = %d, %d\n", x, uni[x], ~uni[x]);
return ~uni[x] ? uni[x] = guni(uni[x]) : x;
}
TREE() {
memset(par, 0, sizeof(par));
memset(uni, -1, sizeof(uni));
for(int i = N - 1; i >= 0; i--) for(auto a : ed[i]) if(a > i) {
//printf("%d\n", a);
int x = guni(a);
if(x != i) {
par[0][x] = uni[x] = i;
chi[i].push_back(x);
}
}
for(int i = 1; i < 20; i++) for(int j = 0; j < N; j++) par[i][j] = par[i - 1][par[i - 1][j]];
dfs(0, 1);
//for(int i = 0; i < N; i++) printf("%d ", dfn[i]);
//printf("\n");
}
int gr(int x, int l) {
for(int i = 19; i >= 0; i--) if(par[i][x] >= l) x = par[i][x];
return x;
}
};
void updbit(int x) { for(; x <= N; x += rb(x)) bit[x]++; }
int gbit(int x) {
int ans = 0;
for(; x; x -= rb(x)) ans += bit[x];
return ans;
}
int gbit(int x, int y) { return gbit(y) - gbit(x - 1); }
vector<int> check_validity(int NN, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
N = NN;
int M = X.size(), Q = S.size();
//printf("*\n");
for(int i = 0; i < M; i++) {
ed[X[i]].push_back(Y[i]);
ed[Y[i]].push_back(X[i]);
}
TREE hm = TREE();
for(int i = 0; i < N; i++) ed[i].clear();
for(int i = 0; i < M; i++) {
ed[N - X[i] - 1].push_back(N - Y[i] - 1);
ed[N - Y[i] - 1].push_back(N - X[i] - 1);
}
TREE ww = TREE();
for(int i = 0; i < N; i++) dot[hm.dfn[i]] = ww.dfn[N - i - 1];
//for(int i = 1; i <= N; i++) printf("%d ", dot[i]);
for(int i = 0; i < Q; i++) {
int t = hm.gr(S[i], L[i]);
qry[hm.dfn[t] - 1].push_back(- i - 1);
qry[hm.dfr[t]].push_back(i);
t = ww.gr(N - E[i] - 1, N - R[i] - 1);
u[i] = hm.dfr[t];
d[i] = hm.dfn[t];
}
vector<int> ans(Q);
for(int i = 0; i <= N; i++) {
if(i) updbit(dot[i]);
for(auto a : qry[i]) {
if(a >= 0) ans[a] += gbit(d[a], u[a]);
else ans[-a - 1] -= gbit(d[-a - 1], u[-a - 1]);
}
}
for(auto &a : ans) a = min(a,1);
return ans;
//return X;
}
