#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int MX = 2e5 + 100;
vector<int> G[MX], G_mx[MX], G_mn[MX];
int boss_mx[MX], boss_mn[MX];
int l_mx[MX], r_mx[MX], l_mn[MX], r_mn[MX], tmp[MX];
vector<int> ptr_mn[MX], ptr_mx[MX];
vector<int> T[MX * 4];
void build_ptr_mn(int u, int p, int &ptr) {
l_mn[u] = ++ptr;
tmp[ptr] = u;
if(p != -1) {
ptr_mn[u].push_back(p);
while(ptr_mn[ptr_mn[u].back()].size() >= ptr_mn[u].size()) {
ptr_mn[u].push_back(ptr_mn[ptr_mn[u].back()][ptr_mn[u].size() - 1]);
}
}
for(auto it: G_mn[u]) build_ptr_mn(it, u, ptr);
r_mn[u] = ptr;
}
void build_ptr_mx(int u, int p, int &ptr) {
l_mx[u] = ++ptr;
if(p != -1) {
ptr_mx[u].push_back(p);
while(ptr_mx[ptr_mx[u].back()].size() >= ptr_mx[u].size()) {
ptr_mx[u].push_back(ptr_mx[ptr_mx[u].back()][ptr_mx[u].size() - 1]);
}
}
for(auto it: G_mx[u]) build_ptr_mx(it, u, ptr);
r_mx[u] = ptr;
}
void build_T(int u, int l, int r) {
if(l == r) return T[u] = {l_mx[tmp[l]]}, void();
int m = l + r >> 1;
build_T(u * 2 + 1, l, m);
build_T(u * 2 + 2, m + 1, r);
T[u].resize(r - l + 1);
merge(T[u * 2 + 1].begin(), T[u * 2 + 1].end(), T[u * 2 + 2].begin(), T[u * 2 + 2].end(), T[u].begin());
}
int query_T(int u, int l, int r, int s, int t, int a, int b) {
if(l == s and r == t) return lower_bound(T[u].begin(), T[u].end(), a) != upper_bound(T[u].begin(), T[u].end(), b);
int m = l + r >> 1;
if(t <= m) return query_T(u * 2 + 1, l, m, s, t, a, b);
if(s > m) return query_T(u * 2 + 2, m + 1, r, s, t, a, b);
return query_T(u * 2 + 1, l, m, s, m, a, b) | query_T(u * 2 + 2, m + 1, r, m + 1, t, a, b);
}
vector<int> query(int N, vector<int> S, vector<int> T, vector<int> L, vector<int> R) {
vector<int> ans;
for(int i = 0; i < S.size(); i ++) {
for(int j = 2000; j >= 0; j --) {
if(ptr_mn[S[i]].empty()) break;
j = min(j, (int) ptr_mn[S[i]].size() - 1);
if(ptr_mn[S[i]][j] >= L[i]) S[i] = ptr_mn[S[i]][j];
}
for(int j = 2000; j >= 0; j --) {
if(ptr_mx[T[i]].empty()) break;
j = min(j, (int) ptr_mx[T[i]].size() - 1);
if(ptr_mx[T[i]][j] <= R[i]) T[i] = ptr_mx[T[i]][j];
}
ans.push_back(query_T(0, 1, N, l_mn[S[i]], r_mn[S[i]], l_mx[T[i]], r_mx[T[i]]));
}
return ans;
}
int Find_mx(int u) {
return boss_mx[u] == u ? u : boss_mx[u] = Find_mx(boss_mx[u]);
}
int Find_mn(int u) {
return boss_mn[u] == u ? u : boss_mn[u] = Find_mn(boss_mn[u]);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> T, vector<int> L, vector<int> R) {
for(int i = 0; i < N; i ++) boss_mx[i] = boss_mn[i] = i;
for(int i = 0; i < X.size(); i ++) {
G[X[i]].push_back(Y[i]);
G[Y[i]].push_back(X[i]);
}
for(int i = N - 1; i >= 0; i --) {
for(auto it: G[i]) {
if(it > i and Find_mn(it) != i) {
G_mn[i].push_back(Find_mn(it));
boss_mn[Find_mn(it)] = i;
}
}
}
for(int i = 0; i < N; i ++) {
for(auto it: G[i]) {
if(it < i and Find_mx(it) != i) {
G_mx[i].push_back(Find_mx(it));
boss_mx[Find_mx(it)] = i;
}
}
}
int ptr_mn = 0; build_ptr_mn(0 , -1, ptr_mn);
int ptr_mx = 0; build_ptr_mx(N - 1, -1, ptr_mx);
build_T(0, 1, N);
return query(N, S, T, L, R);
}
