#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+2, MAXM = 4e5+2, Log = 20;
vector<int> ans;
int Find(int x, vector<int>& f) {
if(f[x] == x) return x;
f[x] = Find(f[x], f);
return f[x];
}
bool Union(int x, int y, vector<int>& f, vector<int>& cnt, vector<int>& mx, bool dir) {
x = Find(x, f); y = Find(y, f);
if(x==y) return false;
if(cnt[x] < cnt[y]) swap(x, y);
cnt[x] += cnt[y];
cnt[y] = 0;
f[y] = x;
if(!dir) {
mx[x] = max(mx[x], mx[y]);
}
else {
mx[x] = min(mx[x], mx[y]);
}
return true;
}
struct Query {
int l, r, id;
};
const int base = (1<<19);
int tree[2*base+1];
void ins(int x, int val) {
x += base;
while(x) {
tree[x]+=val;
x /= 2;
}
}
int qry(int l, int r) {
l+=base; r+=base;
int res = tree[l]; if(l==r) return res;
res += tree[r];
while(l/2 != r/2) {
if(l%2==0) res += tree[l+1];
if(r%2==1) res += tree[r-1];
l /= 2;
r /= 2;
}
return res;
}
vector<int> *occ[MAXN];
struct Form {
vector<vector<int>> g, anc;
vector<vector<Query>> queries;
vector<int> pre, range, subt;
int N, nr=0;
Form *other;
Form(int _N) {
N = _N;
g.resize(N); anc.resize(Log, vector<int>(N));
pre.resize(N); range.resize(N); subt.resize(N);
queries.resize(N);
}
void build_graph(vector<int>& X, vector<int>& Y, vector<int>& order) {
int M = X.size();
vector<int> f(N), cnt(N), mx(N); for(int i=0; i<N; ++i) f[i] = mx[i] = i, cnt[i]=1;
vector<vector<int>> G(N);
for(int i=0; i<M; ++i) {
if( (X[i] < Y[i]) != (order[0] < order.back()) ) {
swap(X[i], Y[i]);
}
G[Y[i]].push_back(X[i]);
}
for(int i: order) {
for(int j: G[i]) {
int repj = mx[Find(j, f)];
if(Union(i, j, f, cnt, mx, (order[0] > order.back()) )) {
g[i].push_back(repj);
}
}
}
}
void build_anc() {
for(int j=1; j<Log; ++j) {
for(int i=0; i<N; ++i) {
anc[j][i] = anc[j-1][anc[j-1][i]];
}
}
}
void dfs(int x, int par) {
anc[0][x] = par;
pre[x] = nr; nr++;
range[x] = pre[x];
subt[x] = 1;
for(int i: g[x]) {
dfs(i, x);
range[x] = max(range[x], range[i]);
subt[x] += subt[i];
}
if(x==par) {
build_anc();
}
}
int lowest_ancestor(int x, int h) {
for(int i=Log-1; i>=0; --i) {
if(x==h) break;
if(anc[i][x]==h || (x < h) == (anc[i][x] < h)) {
x = anc[i][x];
}
}
return x;
}
void solve(int x, int p, bool keep) {
int big_child = -1;
for(int i: g[x]) {
if(big_child==-1 || subt[i] > subt[big_child]) {
big_child = i;
}
}
for(int i: g[x]) {
if(i!=big_child) {
solve(i, x, 0);
}
}
if(big_child==-1) {
occ[x] = new vector<int>();
}
else {
solve(big_child, x, 1);
occ[x] = occ[big_child];
}
for(int i: g[x]) {
if(i!=big_child) {
for(int j: *occ[i]) {
occ[x] -> push_back(j);
ins(j, 1);
}
}
}
occ[x] -> push_back(other->pre[x]);
ins(other->pre[x], 1);
for(auto q: queries[x]) {
ans[q.id] = (qry(q.l, q.r) > 0);
}
if(!keep) {
for(int j: *occ[x]) {
ins(j, -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) {
swap(S, E); // == swap(human, wolf)
int Q = S.size();
ans.resize(Q);
vector<int> order;
for(int i=0; i<N; ++i) order.push_back(i);
Form human(N), wolf(N);
wolf.other = &human;
human.build_graph(X, Y, order);
reverse(order.begin(), order.end());
wolf.build_graph(X, Y, order);
human.dfs(N-1, N-1);
wolf.dfs(0, 0);
for(int i=0; i<Q; ++i) {
S[i] = human.lowest_ancestor(S[i], R[i]);
E[i] = wolf.lowest_ancestor(E[i], L[i]);
if(S[i] > R[i] || E[i] < L[i]) continue;
wolf.queries[E[i]].push_back({human.pre[S[i]], human.range[S[i]], i});
}
wolf.solve(0, 0, 0);
return ans;
}
