#include <bits/stdc++.h>
using namespace std;
struct MaxSegTree {
int n;
vector<int> st;
void build(int v, int vl, int vr, vector<int> &a) {
if (vl == vr) {
st[v] = a[vl];
return;
}
int vm = (vl + vr) / 2;
build(v * 2, vl, vm, a);
build(v * 2 + 1, vm + 1, vr, a);
st[v] = max(st[v * 2], st[v * 2 + 1]);
}
MaxSegTree(int n, vector<int> a) {
this->n = n;
st.resize(4 * n);
build(1, 0, n - 1, a);
}
int get(int l, int r, int v, int vl, int vr) {
if (vr < l || r < vl) return -1e9;
if (l <= vl && vr <= r) return st[v];
int vm = (vl + vr) / 2;
return max(get(l, r, v * 2, vl, vm), get(l, r, v * 2 + 1, vm + 1, vr));
}
};
void dfs(int v, int mn, int mx, vector<vector<int>> &g, vector<bool> &uu) {
if (uu[v] || v > mx || v < mn) return;
uu[v] = 1;
for (int u : g[v]) {
dfs(u, mn, mx, g, uu);
}
}
vector<int> def(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
vector<vector<int>> g(N);
for (int i = 0; i < X.size(); i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
int q = S.size();
vector<int> ans(q);
for (int t = 0; t < q; t++) {
vector<bool> uuw(N), uuh(N);
dfs(E[t], 0, R[t], g, uuw);
dfs(S[t], L[t], N, g, uuh);
for (int i = 0; i < N; i++) {
if (uuw[i] && uuh[i]) ans[t] = 1;
}
}
return ans;
}
vector<int> segt(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int q = S.size();
vector<vector<int>> g(N);
for (int i = 0; i < X.size(); i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
vector<int> a, aT(N);
vector<bool> uu(N);
for (int i = 0; i < N; i++) {
if (g[i].size() == 1) {
a.push_back(i);
aT[i] = 0;
uu[i] = 1;
break;
}
}
for (int i = 1; i < N; i++) {
for (int u : g[a.back()]) {
if (!uu[u]) {
aT[u] = a.size();
a.push_back(u);
uu[u] = 1;
break;
}
}
}
//for (int x : a) cout << x << " ";
//cout << "\n";
MaxSegTree mxst(N, a);
for (int i = 0; i < N; i++) a[i] *= -1;
MaxSegTree mnst(N, a);
vector<int> ans(q);
for (int t = 0; t < q; t++) {
int l, r;
l = -1, r = aT[S[t]];
while (r - l > 1) {
int md = (l + r) / 2;
if (mnst.get(md, aT[S[t]], 1, 0, N - 1) <= -L[t]) r = md;
else l = md;
}
int ls = r;
l = aT[S[t]], r = N;
while (r - l > 1) {
int md = (l + r) / 2;
if (mnst.get(aT[S[t]], md, 1, 0, N - 1) <= -L[t]) l = md;
else r = md;
}
int rs = l;
l = -1, r = aT[E[t]];
while (r - l > 1) {
int md = (l + r) / 2;
if (mxst.get(md, aT[E[t]], 1, 0, N - 1) <= R[t]) r = md;
else l = md;
}
int le = r;
l = aT[E[t]], r = N;
while (r - l > 1) {
int md = (l + r) / 2;
if (mxst.get(aT[E[t]], md, 1, 0, N - 1) <= R[t]) l = md;
else r = md;
}
int re = l;
//cout << t << "\tHUMAN: " << ls << "~" << rs << "\tWOLF: " << le << "~" << re << "\n";
ans[t] = (re >= ls && rs >= le);
}
return ans;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
return segt(N, X, Y, S, E, L, R);
return def(N, X, Y, S, E, L, R);
}
