#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
struct ReachabilityTree {
vector<int> p, sz;
vector<vector<int>> g;
int id;
vector<int> tin, tout;
int timer;
ReachabilityTree(int n) {
n++;
int m = 2 * n + 10;
id = n + 1;
p.assign(m, 0);
sz.assign(m, 1);
g.resize(m);
iota(p.begin(), p.end(), 0);
tin.resize(m);
tout.resize(m);
timer = 0;
}
inline int find(int x) {
return (x == p[x] ? x : p[x] = find(p[x]));
}
inline bool same(int x, int y) {
return find(x) == find(y);
}
inline bool unite(int x, int y) {
if (same(x, y)) return false;
x = find(x);
y = find(y);
if (sz[x] > sz[y]) swap(x, y);
p[x] = id;
p[y] = id;
sz[id] += sz[x] + sz[y];
g[id].push_back(x);
g[id].push_back(y);
id++;
return true;
}
void dfs(int v){
tin[v] = tout[v] = timer++;
for (int u : g[v]){
dfs(u);
tout[v] = tout[u];
}
}
void run_dfs(){
for (int i = 0; i < g.size(); i++){
if (find(i) == i) dfs(i);
}
}
};
struct Fenwick_Tree{
vector<int> f;
Fenwick_Tree(int n){
f.resize(n + 2);
}
void add(int i, int val){
i++;
while (i < (int)f.size()){
f[i] += val;
i += -i & i;
}
}
int get(int i){
i++;
int res = 0;
while (i > 0){
res += f[i];
i -= -i & i;
}
return res;
}
int get(int l, int r){
return get(r) - get(l - 1);
}
};
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int M = X.size(), Q = S.size();
vector<vector<int>> g(N);
for (int i = 0; i < M; i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
vector<vector<int>> q1(N), q2(N);
vector<int> r1(Q), r2(Q);
for (int i = 0; i < Q; i++){
q1[L[i]].push_back(i);
q2[R[i]].push_back(i);
}
ReachabilityTree t1(N), t2(N);
for (int i = N - 1; i >= 0; i--){
for (int j : g[i]){
if (j > i) t1.unite(i, j);
}
for (int j : q1[i]){
r1[j] = t1.find(S[j]);
}
}
for (int i = 0; i < N; i++){
for (int j : g[i]){
if (j < i) t2.unite(i, j);
}
for (int j : q2[i]){
r2[j] = t2.find(E[j]);
}
}
t1.run_dfs();
t2.run_dfs();
int m = 2 * N + 10;
vector<vector<int>> points(m);
for (int i = 0; i < N; i++){
int x = t1.tin[i], y = t2.tin[i];
points[x].push_back(y);
}
vector<vector<pair<int, int>>> queries(m);
for (int i = 0; i < Q; i++){
int x1 = t1.tin[r1[i]], x2 = t1.tout[r1[i]];
int y1 = t2.tin[r2[i]], y2 = t2.tout[r2[i]];
if (x1 > 0) queries[x1 - 1].emplace_back(y1, y2);
queries[x2].emplace_back(y1, y2);
}
Fenwick_Tree f(m);
vector<map<pair<int, int>, int>> mp(m);
for (int x = 0; x < m; x++){
for (int y : points[x]) f.add(y, 1);
for (auto now : queries[x]){
int y1 = now.first, y2 = now.second;
mp[x][make_pair(y1, y2)] = f.get(y1, y2);
}
}
vector<int> ans(Q, 0);
for (int i = 0; i < Q; i++){
int x1 = t1.tin[r1[i]], x2 = t1.tout[r1[i]];
int y1 = t2.tin[r2[i]], y2 = t2.tout[r2[i]];
int inside = mp[x2][make_pair(y1, y2)];
if (x1 > 0) inside -= mp[x1 - 1][make_pair(y1, y2)];
ans[i] = (inside > 0);
}
return ans;
}
