#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5;
vector<int>vec,g[MAXN];
int pos[MAXN];
int mn[MAXN << 2], mx[MAXN << 2];
void dfs (int v, int p = -1) {
vec.push_back (v);
for (int to : g[v]) if (to != p) dfs (to, v);
}
void build (int l = 0, int r = vec.size(), int v = 0) {
if (r - l == 1) { mn[v] = mx[v] = vec[l]; return; }
int m = (l + r) >> 1;
build (l, m, v + v + 1), build (m, r, v + v + 2);
mn[v] = min (mn[v + v + 1], mn[v + v + 2]);
mx[v] = max (mx[v + v + 1], mx[v + v + 2]);
}
int getmn (int L, int R, int l = 0, int r = vec.size(), int v = 0) {
if (L <= l && r <= R) return mn[v];
if (L >= r || l >= R) return MAXN;
int m = (l + r) >> 1;
return min (getmn (L, R, l, m, v + v + 1), getmn (L, R, m, r, v + v + 2));
}
int getmx (int L, int R, int l = 0, int r = vec.size(), int v = 0) {
if (L <= l && r <= R) return mx[v];
if (L >= r || l >= R) return -MAXN;
int m = (l + r) >> 1;
return max (getmx (L, R, l, m, v + v + 1), getmx (L, R, m, r, v + v + 2));
}
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 M = X.size();
for (int i = 0 ; i < M ; ++ i) {
g[X[i]].push_back (Y[i]);
g[Y[i]].push_back (X[i]);
}
int root;
for (int i = 0 ; i < N ; ++ i) {
if (g[i].size() == 1) root = i;
}
dfs(root);
assert (vec.size() == N);
build();
for (int i = 0 ; i < N ; ++ i) {
pos[vec[i]] = i;
}
int Q = S.size();
vector<int>ans(Q);
for (int i = 0 ; i < Q ; ++ i) {
int s = S[i], e = E[i];
int l = pos[s], r = pos[e], res = 0;
if (l <= r) {
while (l <= r) {
int m = (l + r) >> 1;
bool lf = (getmn (pos[s], m + 1) >= L[i]);
bool rg = (getmx (m, pos[e] + 1) <= R[i]);
if (lf && rg) {
res = 1;
break;
}
if (!lf) r = m - 1;
else l = m + 1;
}
} else {
swap (l, r);
swap (s, e);
while (l <= r) {
int m = (l + r) >> 1;
bool lf = (getmn (pos[s], m + 1) <= R[i]);
bool rg = (getmx (m, pos[e] + 1) >= L[i]);
if (lf && rg) {
res = 1;
break;
}
if (!lf) r = m - 1;
else l = m + 1;
}
}
ans[i] = res;
}
return ans;
}
