#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200005, LG = 18;
int n, q, p[2 * N], tim[2][2 * N], sgs[2][2 * N], sge[2][2 * N], cnt;
int sp[2][LG][N];
vector<int> e[N], t[2 * N];
struct Qry{ int i, s, e, sgn; };
vector<Qry> qv[N];
vector<int> pos[N];
int f(int x){ return p[x] = (x == p[x] ? x : f(p[x])); }
void aft(int id, int x){
if(x < n){
sgs[id][x] = sge[id][x] = ++cnt;
return;
}
sgs[id][x] = N;
for(int i : t[x]){
aft(id, i);
sgs[id][x] = min(sgs[id][x], sgs[id][i]);
sge[id][x] = max(sge[id][x], sge[id][i]);
}
}
struct Fen{
int d[N];
void u(int x){ for(; x < N; x += x & -x) d[x]++; }
int g(int x){ int r = 0; for(; x; x &= x - 1) r += d[x]; return r; }
int g(int s, int e){ return g(e) - g(s - 1); }
} F;
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
n = N;
q = S.size();
for(int i = 0; i < X.size(); i++){
e[X[i]].push_back(Y[i]);
e[Y[i]].push_back(X[i]);
}
iota(p, p + 2 * n, 0);
cnt = n;
for(int i = 1; i < n; i++){
for(int j : e[i]){
if(j > i || f(j) == f(i)) continue;
int x = f(i), y = f(j);
sp[0][0][x] = sp[0][0][y] = p[x] = p[y] = cnt;
tim[0][cnt] = i;
t[cnt].push_back(x);
t[cnt].push_back(y);
cnt++;
}
}
cnt = 0;
aft(0, 2 * n - 2);
iota(p, p + 2 * n, 0);
for(int i = 0; i < 2 * n; i++) t[i].clear();
cnt = n;
for(int i = n - 2; i >= 0; i--){
for(int j : e[i]){
if(j < i || f(j) == f(i)) continue;
int x = f(i), y = f(j);
sp[1][0][x] = sp[1][0][y] = p[x] = p[y] = cnt;
tim[1][cnt] = i;
t[cnt].push_back(x);
t[cnt].push_back(y);
cnt++;
}
}
cnt = 0;
aft(1, 2 * n - 2);
for(int id = 0; id < 2; id++){
sp[id][0][2 * n - 2] = 2 * n - 2;
for(int j = 1; j < LG; j++){
for(int k = 0; k < 2 * n - 1; k++){
sp[id][j][k] = sp[id][j - 1][sp[id][j - 1][k]];
}
}
}
for(int i = 0; i < n; i++) pos[sgs[0][i]].push_back(sgs[1][i]);
for(int i = 0; i < q; i++){
int x = S[i];
for(int j = LG-1; j >= 0; j--) if(tim[1][sp[1][j][x]] >= L[i]) x = sp[1][j][x];
int y = E[i];
for(int j = LG-1; j >= 0; j--) if(tim[0][sp[0][j][y]] <= R[i]) y = sp[0][j][y];
qv[sgs[0][y] - 1].push_back({i, sgs[1][x], sge[1][x], -1});
qv[sge[0][y]].push_back({i, sgs[1][x], sge[1][x], 1});
}
vector<int> res(q, 0);
for(int i = 1; i <= n; i++){
for(int j : pos[i]) F.u(j);
for(Qry &j : qv[i]) res[j.i] += j.sgn * F.g(j.s, j.e);
}
for(int &i : res) i = !!i;
return res;
}
