#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const int logn = log2(maxn) + 1;
vector<int> e[maxn] , adj[maxn] , radj[maxn];
int lab[maxn];
int in[2][maxn] , out[2][maxn] , id[2][maxn];
int nTime = 0;
int P[2][maxn][logn];
int n;
#define pb push_back
void DFS(int u , int par , vector<int> adj[] , int in[] , int out[] , int id[] , int P[maxn][logn]){
P[u][0] = par;
for(int i = 1 ; i < logn ; ++i){
if(P[u][i - 1] >= 0 && P[u][i - 1] < n)P[u][i] = P[P[u][i - 1]][i - 1];
else P[u][i] = P[u][i - 1];
}
in[u] = ++nTime;
id[nTime] = u;
for(int c : adj[u]){
DFS(c , u , adj , in , out, id , P);
}
out[u] = nTime;
}
int bit[maxn];
void add(int x){
for(;x <= n ;x += x & -x){
bit[x]++;
}
}
int query(int x){
int res = 0;
for( ; x > 0 ; x &= x - 1){
res += bit[x];
}
return res;
}
vector<tuple<int,int,int,int>> a[maxn];
vector<int> check_validity(int _n, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
n = _n;
for(int i = 0 ; i < (int)X.size() ; ++i){
e[X[i]].pb(Y[i]);
e[Y[i]].pb(X[i]);
}
fill_n(lab,maxn,-1);
function<int(int)> FindLab = [&](int u){
return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);
};
auto add = [&](int x , int y , vector<int> adj[]){
int s = FindLab(x);
int d = FindLab(y);
if(s == d)return;
lab[d] = s;
adj[s].pb(d);
};
for(int i = 0 ; i < n ; ++i){
for(int c : e[i]){
if(c < i)add(i , c , radj);
}
}
fill_n(lab,maxn,-1);
for(int i = n - 1 ; i >= 0 ; --i){
for(int c : e[i]){
if(c > i)add(i , c , adj);
}
}
DFS(0 , -1 , adj , in[0] , out[0] , id[0] , P[0]);
nTime = 0;
DFS(n - 1 , n , radj , in[1] , out[1] , id[1] , P[1]);
int q = S.size();
vector<int> res(q , 0);
for(int i = 0 ; i < q ; ++i){
int s = S[i];int e = E[i];
for(int j = logn - 1 ; j >= 0 ; --j){
if(P[0][s][j] >= L[i])s = P[0][s][j];
if(P[1][e][j] <= R[i])e = P[1][e][j];
}
a[in[0][s] - 1].emplace_back(-1 , in[1][e] , out[1][e] , i);
a[out[0][s]].emplace_back(1 , in[1][e] , out[1][e] , i);
}
for(int i = 1 ; i <= n ; ++i){
::add(in[1][id[0][i]]);
// cout << in[1][id[0][i]] << endl;
for(auto & c : a[i]){
int delta , l , r , id;
tie(delta , l , r , id) = c;
res[id] += delta * (query(r) - query(l - 1));
}
}
for(int i = 0 ; i < q ; ++i){
res[i] = res[i] > 0;
}
return res;
}
