#include <bits/stdc++.h>
#include "werewolf.h"
//~ #include "grader.cpp"
using namespace std;
const int N = 400001;
struct dsu{
int n, p[N], l[N], r[N], t;
vector <int> v[N], perm;
void resize(int _n){
n = _n;
t = 0;
for(int i = 0 ; i < 2 * n ; i++){
p[i] = i;
}
}
int find(int x){
if(p[x] == x) return x;
return p[x] = find(p[x]);
}
void merge(int x, int y){
x = find(x);
y = find(y);
if(x == y) return;
v[n].push_back(x);
v[n].push_back(y);
p[x] = n;
p[y] = n;
n++;
}
void dfs(int node){
perm.push_back(node);
l[node] = t++;
for(auto &i : v[node]){
dfs(i);
}
r[node] = t - 1;
}
void dfs(){
dfs(n - 1);
}
};
struct segment{
int n, tree[2 * N];
void resize(int _n){
n = _n;
}
void update(int p, int v){
for(tree[p += n] = v ; p > 1 ; p >>= 1){
tree[p >> 1] = tree[p] + tree[p ^ 1];
}
}
int query(int l, int r){
r++;
int ret = 0;
for(l += n, r += n ; l < r ; l >>= 1, r >>= 1){
if(l & 1) ret += tree[l++];
if(r & 1) ret += tree[--r];
}
return ret;
}
};
vector <int> v[N], g[N];
vector <pair <int, int> > q, h[N];
dsu a, b;
segment tree;
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
a.resize(N);
b.resize(N);
int M = X.size(), Q = S.size();
for(int i = 0 ; i < M ; i++){
v[X[i]].push_back(Y[i]);
v[Y[i]].push_back(X[i]);
}
q.resize(S.size());
for(int i = 0 ; i < Q ; i++){
g[L[i]].push_back(i);
}
for(int i = N - 1 ; i >= 0 ; i--){
for(auto &j : v[i]){
if(j > i){
a.merge(i, j);
}
}
for(auto &j : g[i]){
q[j].first = a.find(S[j]);
}
g[i].clear();
}
for(int i = 0 ; i < Q ; i++){
g[R[i]].push_back(i);
}
for(int i = 0 ; i < N ; i++){
for(auto &j : v[i]){
if(j < i){
b.merge(i, j);
}
}
for(auto &j : g[i]){
q[j].second = b.find(E[j]);
}
g[i].clear();
}
a.dfs();
b.dfs();
vector <int> pos(2 * N - 1);
for(int i = 0 ; i < 2 * N - 1 ; i++){
pos[b.perm[i]] = i;
}
tree.resize(2 * N - 1);
for(int i = 0 ; i < Q ; i++){
h[a.r[q[i].first]].push_back(make_pair(i, 1));
if(a.l[q[i].first] > 0){
h[a.l[q[i].first] - 1].push_back(make_pair(i, -1));
}
}
vector <int> ans(Q);
for(int i = 0 ; i < 2 * N - 1 ; i++){
if(a.perm[i] < N) tree.update(pos[a.perm[i]], 1);
for(auto &j : h[i]){
ans[j.first] += tree.query(b.l[q[j.first].second], b.r[q[j.first].second]) * j.second;
}
}
for(auto &i : ans) i = i > 0;
return ans;
}
