#include "werewolf.h"
#include <bits/stdc++.h>
struct Dsu {
std::vector <int> p;
std::vector <std::vector <int>> g;
std::vector <int> tour;
std::vector <int> l, r;
inline Dsu(int s) {
p.resize(s);
std::iota(p.begin(), p.end(), 0);
g.resize(s);
l.resize(s);
r.resize(s);
}
inline int find(int v) {
return v == p[v] ? v : (p[v] = find(p[v]));
}
inline void unite(int u, int v) {
if ((u = find(u)) != (v = find(v))) {
g[u].push_back(v);
p[v] = u;
}
}
void make(int node) {
l[node] = tour.size();
tour.push_back(node);
for (int x : g[node]) {
make(x);
}
r[node] = tour.size();
}
};
struct Rag {
int size;
std::vector <std::vector <int>> v;
Rag(const std::vector <int>& a) {
size = 1;
while (size < (int) a.size()) {
size <<= 1;
}
v.resize(size << 1);
make(a, 0, 0, size = a.size());
}
void make(const std::vector <int>& a, int now, int l, int r) {
if (!(r - l - 1)) {
v[now].push_back(a[l]);
return;
}
int mid = (l + r) >> 1;
make(a, now * 2 + 1, l, mid);
make(a, now * 2 + 2, mid, r);
for (int lp = 0, rp = 0;
lp < (int) v[now * 2 + 1].size() || rp < (int) v[now * 2 + 2].size(); ) {
if (lp == (int) v[now * 2 + 1].size()) v[now].push_back(v[now * 2 + 2][rp++]);
else if (rp == (int) v[now * 2 + 2].size()) v[now].push_back(v[now * 2 + 1][lp++]);
else if (v[now * 2 + 1][lp] < v[now * 2 + 2][rp]) v[now].push_back(v[now * 2 + 1][lp++]);
else v[now].push_back(v[now * 2 + 2][rp++]);
}
}
int query(int tl, int tr, int le, int ri) {
return query(tl, tr, le, ri, 0, 0, size);
}
int query(int tl, int tr, int le, int ri, int now, int l, int r) {
if (l >= tr || r <= tl) {
return 0;
}
if (l >= tl && r <= tr) {
return
std::lower_bound(v[now].begin(), v[now].end(), ri) -
std::lower_bound(v[now].begin(), v[now].end(), le);
}
int mid = (l + r) >> 1;
return query(tl, tr, le, ri, now * 2 + 1, l, mid) + query(tl, tr, le, ri, now * 2 + 2, mid, r);
}
};
std::vector <int> check_validity(int n, std::vector <int> _u, std::vector <int> _v,
std::vector <int> s, std::vector <int> e, std::vector <int> l, std::vector <int> r) {
int m = _u.size();
int q = s.size();
std::vector <std::vector <int>> g(n), ql(n), qr(n);
std::vector <int> pl(q), pr(q), tord(n), initial(n), ans(q);
Dsu dsul(n), dsur(n);
for (int i = 0; i < m; i++) {
g[_u[i]].push_back(_v[i]);
g[_v[i]].push_back(_u[i]);
}
for (int i = 0; i < q; i++) {
ql[l[i]].push_back(i);
qr[r[i]].push_back(i);
}
for (int i = 0; i < n; i++) {
for (int x : g[n - i - 1]) {
if (x > n - i - 1) {
dsul.unite(n - i - 1, x);
}
}
for (int x : ql[n - i - 1]) {
pl[x] = dsul.find(s[x]);
}
for (int x : g[i]) {
if (x < i) {
dsur.unite(i, x);
}
}
for (int x : qr[i]) {
pr[x] = dsur.find(e[x]);
}
}
dsul.make(dsul.find(0));
dsur.make(dsur.find(0));
for (int i = 0; i < n; i++) {
tord[dsul.tour[i]] = i;
}
for (int i = 0; i < n; i++) {
initial[i] = tord[dsur.tour[i]];
}
Rag rag(initial);
for (int i = 0; i < q; i++) {
ans[i] = !!rag.query(dsur.l[pr[i]], dsur.r[pr[i]], dsul.l[pl[i]], dsul.r[pl[i]]);
}
return ans;
}
