#define DEBUG 0
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef pair <pii, pii> ppp;
const int INF=0x3f3f3f3f;
const int N=2e5+5;
int n, m, q, uk, dt;
int P[2*N], roots[N], lef[2*N], rig[2*N], F[2*N];
vector <int> ls[N], dj[2*N], toc[2*N], sol;
vector <pii> que[N];
vector <ppp> duz[2*N];
pii p[N], r_x[N], r_y[N];
int query(int x) {
int ret=0;
for (x++; x>0; x-=x&-x) ret+=F[x];
return ret;
}
void update(int x, int val) {
for (x++; x<=2*n+2; x+=x&-x) F[x]+=val;
}
int name(int x) {
if (x==P[x]) return x;
P[x]=name(P[x]);
return P[x];
}
void dfs(int node) {
lef[node]=dt++;
for (int sus:dj[node]) dfs(sus);
rig[node]=dt-1;
}
vector<int> check_validity(int NN, vector<int> XX, vector<int> YY,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
n=NN;
m=XX.size();
q=L.size();
for (int i=0; i<m; ++i) ls[XX[i]].pb(YY[i]), ls[YY[i]].pb(XX[i]);
for (int i=0; i<2*n; ++i) P[i]=i;
for (int i=0; i<q; ++i) que[L[i]].pb(mp(S[i], i));
uk=n;
for (int i=n-1; i>=0; --i) {
dj[uk].pb(name(i));
#if DEBUG
printf("dijete od %d je %d\n", uk, name(i));
#endif // DEBUG
P[name(i)]=uk;
for (int sus:ls[i]) {
if (sus<=i || name(sus)==uk) continue;
#if DEBUG
printf("dijete od %d je %d\n", uk, name(sus));
#endif // DEBUG
dj[uk].pb(name(sus));
P[name(sus)]=uk;
}
uk++;
for (pii pp:que[i]) roots[pp.Y]=name(pp.X);
}
dt=0;
dfs(name(0));
for (int i=0; i<n; ++i) p[i].X=lef[i];
for (int i=0; i<q; ++i) r_x[i]=mp(lef[roots[i]], rig[roots[i]]);
for (int i=0; i<n; ++i) que[i].clear();
for (int i=0; i<2*n; ++i) dj[i].clear(), P[i]=i;
for (int i=0; i<q; ++i) que[R[i]].pb(mp(E[i], i));
uk=n, dt=0;
for (int i=0; i<n; ++i) {
dj[uk].pb(name(i));
P[name(i)]=uk;
for (int sus:ls[i]) {
if (sus>=i || name(sus)==uk) continue;
dj[uk].pb(name(sus));
P[name(sus)]=uk;
}
uk++;
for (pii pp:que[i]) roots[pp.Y]=name(pp.X);
}
dfs(name(0));
for (int i=0; i<n; ++i) {
p[i].Y=lef[i];
toc[p[i].X].pb(p[i].Y);
}
for (int i=0; i<q; ++i) {
r_y[i]=mp(lef[roots[i]], rig[roots[i]]);
if (r_x[i].X) duz[r_x[i].X-1].pb(mp(r_y[i], mp(-1, i)));
duz[r_x[i].Y].pb(mp(r_y[i], mp(1, i)));
}
sol.resize(q, 0);
for (int i=0; i<2*n; ++i) {
for (int y:toc[i]) update(y, 1);
for (ppp pp:duz[i]) sol[pp.Y.Y]+=(query(pp.X.Y)-query(pp.X.X-1))*pp.Y.X;
}
for (int i=0; i<q; ++i) sol[i]=!!sol[i];
return sol;
}
