#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 6e5 + 5;
struct BIT {
int n;
vector<int> tree;
void config(int _n) {
n = _n + 10;
tree.resize(_n+60);
}
void update(int p, int v) {
for(p++; p<n; p+=p&-p) tree[p] += v;
}
int query(int p) {
int ans = 0;
for(p++; p>0; p-=p&-p) ans += tree[p];
return ans;
}
int query(int l, int r) { return query(r) - query(l-1); }
};
int par[2][maxn], n, d[2][maxn], mn[maxn], mx[maxn], out[2][maxn], up[2][maxn][21], in[2][maxn], timer[2];
vector<int> graph[2][maxn], euler[2];
vector<int> by_x[maxn+5];
int find(int u, int t) {
if(par[t][u] == u) return u;
return par[t][u] = find(par[t][u], t);
}
void uni(int a, int b, int t) {
a = find(a, t); b = find(b, t);
if(a == b) return ;
n++;
par[t][n] = par[t][a] = par[t][b] = n;
graph[t][n].push_back(a);
graph[t][n].push_back(b);
}
void dfs(int u, int t) {
if(graph[t][u].empty()) {
if(t == 0) mn[u] = u;
else mx[u] = u;
}
in[t][u] = timer[t]++; euler[t].push_back(u);
for(int i=1; i<21; i++) up[t][u][i] = up[t][up[t][u][i-1]][i-1];
for(int &v : graph[t][u]) {
d[t][v] = d[t][u] + 1;
up[t][v][0] = u;
dfs(v, t);
if(t == 0) mn[u] = min(mn[u], mn[v]);
else mx[u] = max(mx[u], mx[v]);
}
out[t][u] = timer[t] - 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) {
int Q = S.size(), M = X.size();
vector<int> ans(Q);
for(int i=1; i<=N+M; i++) par[0][i] = par[1][i] = i, mn[i] = 1e9;
vector<int> edges[N+1];
for(int i=0; i<M; i++) {
edges[X[i]+1].push_back(Y[i]+1);
edges[Y[i]+1].push_back(X[i]+1);
}
n = N;
for(int i=N; i>=1; i--)
for(int &j : edges[i]) if(i < j) uni(i, j, 0);
n = N;
for(int i=1; i<=N; i++)
for(int &j : edges[i]) if(i > j) uni(i, j, 1);
dfs(n, 0); dfs(n, 1);
vector<array<int, 4> > qus;
for(int i=1; i<=N; i++) by_x[in[0][i]].push_back(in[1][i]);
for(int i=0; i<Q; i++) {
S[i]++; E[i]++; L[i]++; R[i]++;
if(S[i] < L[i] || E[i] > R[i]) continue;
int p1 = S[i], p2 = E[i];
for(int j=20; j>=0; j--) {
if(up[0][p1][j] > 0 && mn[up[0][p1][j]] >= L[i]) p1 = up[0][p1][j];
if(up[1][p2][j] > 0 && mx[up[1][p2][j]] <= R[i]) p2 = up[1][p2][j];
}
qus.push_back({ in[0][p1], out[0][p1], in[1][p2], out[1][p2] });
}
vector<int> on[n+1], off[n+1], add[n+1];
for(int i=0; i<Q; i++) {
on[qus[i][1]].push_back(i);
if(qus[i][0]) off[qus[i][0]-1].push_back(i);
}
BIT bit; bit.config(n+1);
for(int i=0; i<=n; i++) {
for(int &p : by_x[i]) bit.update(p, 1);
for(int &id : off[i]) ans[id] -= bit.query(qus[id][2], qus[id][3]);
for(int &id : on[i]) ans[id] += bit.query(qus[id][2], qus[id][3]);
}
for(int i=0; i<Q; i++) {
if(ans[i] >= 1) ans[i] = 1;
else ans[i] = 0;
}
return ans;
}
