#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int lg = 20;
struct segtree {
vector<int> tree;
segtree(int n) : tree(4*n) {}
void update(int i, int x, int l, int r, int node) {
if (l == r) tree[node] += x;
else {
int m = (l + r) / 2;
if (i <= m) update(i, x, l, m, node<<1);
else update(i, x, m+1, r, node<<1|1);
tree[node] = tree[node<<1] + tree[node<<1|1];
}
}
int qry(int ql, int qr, int l, int r, int node) {
if (ql <= l && r <= qr) return tree[node];
if (r < ql || qr < l) return 0;
int m = (l + r) / 2;
return qry(ql, qr, l, m, node<<1) + qry(ql, qr, m+1, r, node<<1|1);
}
};
struct dsu {
vector<int> id, sz;
dsu(int n) {
for (int i = 0; i < n; i++) {
id.push_back(i);
sz.push_back(1);
}
}
int find(int x) {return x == id[x] ? x : id[x] = find(id[x]);}
void unite(int a, int b) {
a = find(a), b = find(b);
if (a==b) return;
sz[a] += sz[b];
id[b] = a;
}
};
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
//make bigtree and smalltree
int M = X.size();
vector<vector<int>> totadj(N+1), adjsmall(N+1), adjbig(N+1), parsmall(lg, vector<int>(N, -1)), parbig(lg, vector<int>(N, -1));
dsu smalltree(N), bigtree(N);
for (int i = 0; i < M; i++) {
totadj[X[i]].push_back(Y[i]);
totadj[Y[i]].push_back(X[i]);
}
for (int i = 0; i < N; i++) for (int u : totadj[i]) if (u < i) {
int uu = smalltree.find(u);
if (i == uu) continue;
smalltree.unite(i, uu);
parsmall[0][uu] = i;
adjsmall[i].push_back(uu);
}
for (int i = N-1; i >= 0; i--) for (int u : totadj[i]) if (u > i) {
int uu = bigtree.find(u);
if (i == uu) continue;
bigtree.unite(i, uu);
parbig[0][uu] = i;
adjbig[i].push_back(uu);
}
//Now find dfsorder for both trees + BinaryLifting ready
vector<int> smallorder = {0}, bigorder = {0}, possmall(N, 0), posbig(N, 0), subbig(N, 0), subsmall(N, 0), Lsmall(N), Lbig(N), Rsmall(N), Rbig(N);
for (int b = 1; b < lg; b++) for (int i = 0; i < N; i++) {
if (parsmall[b-1][i] != -1) parsmall[b][i] = parsmall[b-1][parsmall[b-1][i]];
if (parbig[b-1][i] != -1) parbig[b][i] = parbig[b-1][parbig[b-1][i]];
}
auto dfs = [&](int node, int tp, auto& dfs) -> void {
if (tp == 0) {
subsmall[node] = 1;
possmall[node] = smallorder.size();
smallorder.push_back(node);
Lsmall[node] = possmall[node];
for (int u : adjsmall[node]) {
dfs(u, tp, dfs);
subsmall[node] += subsmall[u];
}
Rsmall[node] = Lsmall[node] + subsmall[node] - 1;
} else {
subbig[node] = 1;
posbig[node] = bigorder.size();
bigorder.push_back(node);
Lbig[node] = posbig[node];
for (int u : adjbig[node]) {
dfs(u, tp, dfs);
subbig[node] += subbig[u];
}
Rbig[node] = Lbig[node] + subbig[node] - 1;
}
};
for (int i = 0; i < N; i++) {
if (!subsmall[i]) {
int root = i;
for (int b = lg-1; b >= 0; b--) {
if (parsmall[b][root] != -1) root = parsmall[b][root];
}
dfs(root, 0, dfs);
}
if (!subbig[i]) {
int root = i;
for (int b = lg-1; b >= 0; b--) if (parbig[b][root] != -1) root = parbig[b][root];
dfs(root, 1, dfs);
}
}
// Now we want to maintain a segmenttree
//we consider for each int 0 - n-1 the coordinates possmall, posbig
int Q = S.size();
vector<int> res(Q, 0);
vector<vector<vector<int>>> Lqrys(N+1), Rqrys(N+1);
for (int i = 0; i < Q; i++) {
int root1 = S[i], root2 = E[i];
//starting at S, we can only take nodes <= R
for (int b = lg-1; b >= 0; b--) {
if (parsmall[b][root2] != -1 && parsmall[b][root2] <= R[i]) root2 = parsmall[b][root2];
if (parbig[b][root1] != -1 && parbig[b][root1] >= L[i]) root1 = parbig[b][root1];
}
//so now we have our two roots, and for each we also have
//each query is { L, R, idx }
Lqrys[Lsmall[root2]].push_back({Lbig[root1], Rbig[root1], i});
Rqrys[Rsmall[root2]].push_back({Lbig[root1], Rbig[root1], i});
}
segtree seg(N);
for (int i = 1; i <= N; i++) {
//first answer all lefts
for (auto& v : Lqrys[i]) res[v[2]] -= seg.qry(v[0], v[1], 1, N, 1);
//then update our val
seg.update(posbig[smallorder[i]], 1, 1, N, 1);
//Now finish right queries
for (auto& v : Rqrys[i]) res[v[2]] += seg.qry(v[0], v[1], 1, N, 1);
}
for (int i = 0; i < Q; i++) res[i] = res[i] > 0;
return res;
}
