#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int MN = 2e5 + 3;
struct Query {
int l,r,l2,r2,id;
};
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 = (int)x.size(), qq = (int)s.size(), LOG = __lg(n) + 1;
vector<vector<int>> aaa(n+1); array<vector<vector<int>>,2> adj;
for (int j = 0; j < 2; j++) adj[j].resize(n+1);
vector<int> ret(qq);
for (int i = 0; i < m; i++) {
aaa[++x[i]].push_back(++y[i]);
aaa[y[i]].push_back(x[i]);
}
vector<int> p(n+1);
iota(p.begin(),p.end(),0); //1 is for >=, 0 is for <=
const auto find = [&] (int x, const auto &find_ref) -> int {
return p[x] == x ? x : p[x] = find_ref(p[x],find_ref);
};
const auto merge = [&] (int a, int b, bool lt) {
if ((a = find(a,find)) == (b = find(b,find))) return;
if ((a > b) ^ lt) swap(a,b);
p[a] = b; adj[lt][b].push_back(a);
};
for (int i = n; i >= 1; i--) for (int j : aaa[i]) if (j > i) merge(i,j,1);
iota(p.begin(),p.end(),0);
for (int i = 1; i <= n; i++) for (int j : aaa[i]) if (j < i) merge(i,j,0);
int tt = 0; array<vector<int>,2> st,ed,which; array<vector<vector<int>>,2> jmp, par;
for (int i = 0; i < 2; i++) st[i].resize(n+1), ed[i].resize(n+1), which[i].resize(n+1), jmp[i].resize(n+1,vector<int>(LOG));
const auto dfs = [&] (int cur, int p, int id, const auto &dfs_ref) -> void {
which[id][st[id][cur] = ++tt] = cur;
for (int i : adj[id][cur]) if (i != p) {
jmp[id][i][0] = cur;
for (int j = 1; j < LOG; j++)
jmp[id][i][j] = jmp[id][jmp[id][i][j-1]][j-1];
dfs_ref(i,cur,id,dfs_ref);
}
ed[id][cur] = tt;
};
dfs(1,-1,1,dfs);
tt = 0;
dfs(n,-1,0,dfs);
const auto lift = [&] (int cur, int id, int x) {
for (int j = LOG - 1; ~j; j--)
if (jmp[id][cur][j] && (jmp[id][cur][j] == x || (id ^ (jmp[id][cur][j] < x))))
cur = jmp[id][cur][j];
return cur;
};
vector<Query> queries(qq);
for (int i = 0; i < qq; i++) {
int golt = lift(++e[i],0,++r[i]), gogt = lift(++s[i],1,++l[i]);
queries[i] = {st[0][golt],ed[0][golt],st[1][gogt],ed[1][gogt],i};
}
vector<int> tree(n*2);
auto update = [&tree,&n] (int i, int v) {
for (tree[i += n - 1] = v; i > 1; i >>= 1)
tree[i>>1] = max(tree[i],tree[i^1]);
};
auto query = [&tree,&n] (int l, int r) {
int ret = 0;
for (l += n-1, r += n; l < r; l >>= 1, r >>= 1) {
if (l&1) ret = max(ret,tree[l++]);
if (r&1) ret = max(ret,tree[--r]);
}
return ret;
};
sort(queries.begin(),queries.end(),[&](const Query &a, const Query &b){return a.r < b.r;});
int pp = 1;
for (Query &q : queries) {
while (pp <= q.r) {
update(st[1][which[0][pp]],pp);
++pp;
}
ret[q.id] = query(q.l2,q.r2) >= q.l;
}
return ret;
}
