#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
template <typename Fun>
struct YCombinator {
template <typename T>
YCombinator(T &&_fun) : fun(forward<T>(_fun)) {}
template <typename... Args>
decltype(auto) operator()(Args &&...args) {
return fun(ref(*this), forward<Args>(args)...);
}
private:
Fun fun;
};
template <typename T>
YCombinator(T &&) -> YCombinator<decay_t<T>>;
template <typename S, typename Op = plus<S>>
struct FenwickTree {
explicit FenwickTree(int _n = 0, S _e = S(), Op _op = Op()) : n(_n), e(_e), op(_op), tree(n + 1, e) {}
S query(int p) const {
S x = e;
for (; p; p -= p & -p) {
x = op(tree[p], x);
}
return x;
}
S query() const {
return query(n);
}
void modify(int p, S x) {
for (p++; p <= n; p += p & -p) {
tree[p] = op(tree[p], x);
}
}
int size() const {
return n;
}
private:
int n;
S e;
Op op;
vector<S> tree;
};
} // namespace
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 n = N;
int m = (int)X.size();
int q = (int)S.size();
vector<int> a, b;
vector<array<int, 2>> sub_a(q), sub_b(q);
vector<vector<int>> qrys_l(n), qrys_r(n);
for (int i = 0; i < q; i++) {
qrys_l[L[i]].push_back(i);
qrys_r[R[i]].push_back(i);
}
{
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
int u = X[i];
int v = Y[i];
if (u > v) {
swap(u, v);
}
adj[u].push_back(v);
}
vector<vector<int>> krt(2 * n);
vector<int> node(q);
vector<int> root(2 * n);
iota(root.begin(), root.end(), 0);
YCombinator get_root = [&](auto self, int u) -> int {
return root[u] == u ? u : root[u] = self(root[u]);
};
for (int u = n - 1; u >= 0; u--) {
int x = 2 * n - (u + 1);
krt[x].push_back(u);
root[u] = x;
vector<int> ch;
for (int v : adj[u]) {
ch.push_back(get_root(v));
}
sort(ch.begin(), ch.end());
ch.erase(unique(ch.begin(), ch.end()), ch.end());
for (int y : ch) {
krt[x].push_back(y);
root[y] = x;
}
for (int i : qrys_l[u]) {
node[i] = get_root(S[i]);
}
}
vector<int> tin(2 * n), tout(2 * n);
{
int timer = 0;
YCombinator([&](auto self, int x) -> void {
tin[x] = timer;
if (x < n) {
a.push_back(x);
timer++;
}
for (int y : krt[x]) {
self(y);
}
tout[x] = timer;
})(2 * n - 1);
}
for (int i = 0; i < q; i++) {
sub_a[i] = {tin[node[i]], tout[node[i]]};
}
}
{
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
int u = X[i];
int v = Y[i];
if (u < v) {
swap(u, v);
}
adj[u].push_back(v);
}
vector<vector<int>> krt(2 * n);
vector<int> node(q);
vector<int> root(2 * n);
iota(root.begin(), root.end(), 0);
YCombinator get_root = [&](auto self, int u) -> int {
return root[u] == u ? u : root[u] = self(root[u]);
};
for (int u = 0; u < N; u++) {
int x = n + u;
krt[x].push_back(u);
root[u] = x;
vector<int> ch;
for (int v : adj[u]) {
ch.push_back(get_root(v));
}
sort(ch.begin(), ch.end());
ch.erase(unique(ch.begin(), ch.end()), ch.end());
for (int y : ch) {
krt[x].push_back(y);
root[y] = x;
}
for (int i : qrys_r[u]) {
node[i] = get_root(E[i]);
}
}
vector<int> tin(2 * n), tout(2 * n);
{
int timer = 0;
YCombinator([&](auto self, int x) -> void {
tin[x] = timer;
if (x < n) {
b.push_back(x);
timer++;
}
for (int y : krt[x]) {
self(y);
}
tout[x] = timer;
})(2 * n - 1);
}
for (int i = 0; i < q; i++) {
sub_b[i] = {tin[node[i]], tout[node[i]]};
}
}
vector<int> ans(q);
{
vector<int> idx(n);
for (int i = 0; i < n; i++) {
idx[a[i]] = i;
}
vector<array<vector<int>, 2>> todo(n);
for (int i = 0; i < q; i++) {
todo[sub_b[i][0]][0].push_back(i);
todo[sub_b[i][1] - 1][1].push_back(i);
}
FenwickTree<int> fenw(n);
for (int i = 0; i < n; i++) {
for (int j : todo[i][0]) {
ans[j] -= fenw.query(sub_a[j][1]) - fenw.query(sub_a[j][0]);
}
fenw.modify(idx[b[i]], 1);
for (int j : todo[i][1]) {
ans[j] += fenw.query(sub_a[j][1]) - fenw.query(sub_a[j][0]);
}
}
}
for (int i = 0; i < q; i++) {
if (ans[i] > 0) {
ans[i] = 1;
}
}
return ans;
}
