#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
template<typename T>
using v = vector<T>;
const int INF = 1e9;
v<int> h;
v<v<int>> adj;
void dfs(int n, int p=0, int d=0) {
h[n] = d;
for (auto x : adj[n]) {
if (h[x] == -1) {
dfs(x, n, d+1);
}
}
}
int kthmx(int m, v<v<v<int>>> &lift, int rb) {
for (int i = 20; i >= 0; i--) {
if (lift[m][i][1] <= rb) {
m = lift[m][i][0];
}
}
return m;
}
int kthmn(int m, v<v<v<int>>> &lift, int lb) {
for (int i = 20; i >= 0; i--) {
if (lift[m][i][2] >= lb) {
m = lift[m][i][0];
}
}
return m;
}
//inicio esta a la izquierda del termino
bool check1(int a, int b) {
if (a == 0 || b == 0) return true;
else return (h[a] >= h[b]);
}
//inicio esta a la derecha del termino
bool check2(int a, int b) {
if (a == 0 || b == 0) return true;
else return (h[a] <= h[b]);
}
v<int> check_validity(int N, v<int> X, v<int> Y, v<int> S, v<int> E, v<int> L, v<int> R) {
int n = N;
adj.resize(n+1);
int m = X.size();
rep(i, 0, m) {
X[i]++, Y[i]++;
}
rep(i, 0, m){
int a = X[i], b = Y[i];
adj[a].push_back(b);
adj[b].push_back(a);
}
h.assign(n+1, -1);
v<v<v<int>>> leftt(n+1, v<v<int>>(21, v<int>(3)));
v<v<v<int>>> rightt(n+1, v<v<int>>(21, v<int>(3)));
rep(i, 0, n+1) {
rep(j, 0, 21) {
leftt[i][j] = {0, 0, INF};
rightt[i][j] = {0, 0, INF};
}
}
v<int> a(n+1);
int u = 1;
rep(i, 1, n+1) {
if (adj[i].size() == 1) {
u = i;
break;
}
}
dfs(u);
rep(i, 1, n+1) {
a[h[i]] = i;
}
//lift[i][j][0] = 2^j ancestro, lift[i][j][1] = max, lift[i][j][2] = min
rep(i, 0, n) {
if (i == 0) leftt[a[i]][0] = {0, INF, 0};
else leftt[a[i]][0] = {a[i-1], a[i-1], a[i-1]};
if (i == n-1) rightt[a[i]][0] = {0, INF, 0};
else rightt[a[i]][0] = {a[i+1], a[i+1], a[i+1]};
}
rep(j, 1, 21) {
rep(i, 1, n+1) {
//left
leftt[i][j][0] = leftt[leftt[i][j-1][0]][j-1][0];
leftt[i][j][1] = max(leftt[i][j-1][1], leftt[leftt[i][j-1][0]][j-1][1]);
leftt[i][j][2] = min(leftt[i][j-1][2], leftt[leftt[i][j-1][0]][j-1][2]);
//right
rightt[i][j][0] = rightt[rightt[i][j-1][0]][j-1][0];
rightt[i][j][1] = max(rightt[i][j-1][1], rightt[rightt[i][j-1][0]][j-1][1]);
rightt[i][j][2] = min(rightt[i][j-1][2], rightt[rightt[i][j-1][0]][j-1][2]);
}
}
int q = L.size();
v<int> ans(q);
rep(i, 0, q) {
S[i]++; E[i]++;
L[i]++; R[i]++;
}
rep(i, 0, q) {
int s = S[i], e = E[i];
//cout << s << " " << e << endl;
if (h[s] < h[e]) {
int smn = kthmn(s, rightt, L[i]);
int emx = kthmx(e, leftt, R[i]);
if (check1(smn, emx)) ans[i] = 1;
else ans[i] = 0;
}
else {
int smn = kthmn(s, leftt, L[i]);
int emx = kthmx(e, rightt, R[i]);
//cout << smn << " " << emx << endl;
if (check2(smn, emx)) ans[i] = 1;
else ans[i] = 0;
}
}
//for (auto x : ans) cerr << x << " ";
//cout << endl;
return ans;
}
