#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;
};
struct Node {
int l, r, val;
Node *ls = NULL, *rs = NULL;
Node(int _l, int _r) {
l = _l; r = _r; val=0;
}
void push() {
if(!ls) {
ls = new Node(l, (l+r)/2);
rs = new Node((l+r)/2+1, r);
}
}
};
struct Segtree {
vector<int> updates;
Node *root;
Segtree(int _N) {
root = new Node(0, _N-1);
}
void ins(int x, Node* cur) {
if(x > (cur->r) || x < (cur->l)) {
return;
}
cur->val++;
if((cur->l) == (cur->r)) return;
cur->push();
ins(x, cur->ls);
ins(x, cur->rs);
}
void upd(int x) {
updates.push_back(x);
ins(x, root);
}
int qry(int l, int r, Node* cur) {
if(l > (cur->r) || r < (cur->l)) {
return 0;
}
if(l <= (cur->l) && r >= (cur->r)) {
return cur->val;
}
cur->push();
return qry(l, r, cur->ls) + qry(l, r, cur->rs);
}
void clr() {
updates.clear();
}
};
Segtree *occ[MAXN];
struct Form {
vector<vector<int>> g, anc;
vector<vector<Query>> queries;
vector<int> pre, range;
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);
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];
for(int i: g[x]) {
dfs(i, x);
range[x] = max(range[x], range[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) {
int big_child = -1;
for(int i: g[x]) {
solve(i, x);
if(big_child==-1 || occ[i]->updates.size() > occ[big_child]->updates.size()) {
big_child = i;
}
}
if(big_child==-1) {
occ[x] = new Segtree(N);
}
else {
occ[x] = occ[big_child];
}
for(int i: g[x]) {
if(i!=big_child) {
for(int j: occ[i]->updates) {
occ[x]->upd(j);
}
occ[i]->clr();
}
}
occ[x]->upd(other->pre[x]);
for(auto q: queries[x]) {
ans[q.id] = (occ[x]->qry(q.l, q.r, occ[x]->root) > 0);
}
}
};
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);
return ans;
}
