#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
int ti;
vector<int> par, in, out, order;
vector<vector<int>> adj;
DSU(int n) : ti(0), par(n), in(n), out(n), order({n}), adj(n) {
iota(par.begin(), par.end(), 0);
}
int find(int u) {
return u == par[u] ? u : par[u] = find(par[u]);
}
void unite(int u, int v) {
u = find(u);
v = find(v);
if (u == v)
return;
par.push_back((int) par.size());
par[u] = par[v] = (int) par.size() - 1;
in.emplace_back();
out.emplace_back();
adj.push_back({u, v});
}
void dfs(int u) {
in[u] = ++ti;
order.push_back(u);
for (int v : adj[u])
dfs(v);
out[u] = ti;
}
};
template<typename T>
struct BIT {
int n;
vector<T> bit;
BIT(int _n) : n(_n), bit(n + 1) {}
T query(int i) {
T ret = 0;
for (; i>0; i-=i&-i)
ret += bit[i];
return ret;
}
T query(int l, int r) {
return query(r) - query(l-1);
}
void update(int i, T val) {
for (; i<=n; i+=i&-i)
bit[i] += val;
}
};
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
int m = (int) X.size(), q = (int) S.size();
vector<vector<int>> adj(N);
for (int i=0; i<m; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
vector<vector<int>> queryL(N), queryR(N);
for (int i=0; i<q; i++) {
queryL[L[i]].push_back(i);
queryR[R[i]].push_back(i);
}
DSU inc(N), dec(N);
for (int u=0; u<N; u++) {
for (int v : adj[u])
if (v < u)
inc.unite(u, v);
for (int i : queryR[u])
E[i] = inc.find(E[i]);
}
for (int u=N-1; u>=0; u--) {
for (int v : adj[u])
if (v > u)
dec.unite(u, v);
for (int i : queryL[u])
S[i] = dec.find(S[i]);
}
inc.dfs(inc.find(0));
dec.dfs(dec.find(0));
int o1 = (int) inc.order.size(), o2 = (int) dec.order.size();
vector<vector<pair<int, int>>> pts(o1);
BIT<int> bit(o2);
vector<int> ret(q);
for (int i=0; i<q; i++) {
pts[inc.in[E[i]] - 1].emplace_back(i, -1);
pts[inc.out[E[i]]].emplace_back(i, 1);
}
for (int i=0; i<o1; i++) {
if (inc.order[i] < N)
bit.update(dec.in[inc.order[i]], 1);
for (auto [j, c] : pts[i])
ret[j] += bit.query(dec.in[S[j]], dec.out[S[j]]) * c;
}
for (int i=0; i<q; i++)
ret[i] = ret[i] > 0;
return ret;
}
