#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
#define ffor(i, a, b) for (ll i = a; i < b; i++)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()
std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
int Q = S.size();
vii ord(n), pos(n);
vvii adj(n);
rep(i, X.size()) {
adj[X[i]].emplace_back(Y[i]);
adj[Y[i]].emplace_back(X[i]);
}
rep(i, n) {
if (adj[i].size() == 1) {
ord[0] = i;
ord[1] = adj[i][0];
int curr = 1;
while (curr < n - 1) {
forin(x, adj[ord[curr]]) {
if (x != ord[curr - 1]) {
ord[curr + 1] = x;
break;
}
}
curr++;
}
break;
}
}
rep(i, n) {
pos[ord[i]] = i;
}
vii tmin(2 * n), tmax(2 * n);
rep(i, n) {
tmin[n + i] = tmax[n + i] = ord[i];
}
for (int i = n - 1; i >= 1; i--) {
tmin[i] = min(tmin[i * 2], tmin[i * 2 + 1]);
tmax[i] = max(tmax[i * 2], tmax[i * 2 + 1]);
}
auto minquery = [&](int l, int r) {
l += n;
r += n;
int res = n;
while (l < r) {
if (l % 2) res = min(res, tmin[l++]);
if (r % 2) res = min(res, tmin[--r]);
l /= 2;
r /= 2;
}
return res;
};
auto maxquery = [&](int l, int r) { //[l,r)
l += n;
r += n;
int res = -1;
while (l < r) {
if (l % 2) res = max(res, tmax[l++]);
if (r % 2) res = max(res, tmax[--r]);
l /= 2;
r /= 2;
}
return res;
};
vii res(Q);
rep(i, Q) {
if (pos[S[i]] < pos[E[i]]) {
if (minquery(pos[S[i]], pos[E[i]] + 1) >= L[i]) {
res[i] = 1;
continue;
}
int lo = pos[S[i]] + 1, hi = pos[E[i]];
while (lo < hi) {
int mid = (lo + hi) / 2;
if (minquery(pos[S[i]], mid + 1) < L[i]) {
hi = mid;
} else {
lo = mid + 1;
}
}
if (maxquery(lo - 1, pos[E[i]] + 1) <= R[i]) {
res[i] = 1;
}
} else {
swap(S[i], E[i]);
if (maxquery(pos[S[i]], pos[E[i]] + 1) <= R[i]) {
res[i] = 1;
continue;
}
int lo = pos[S[i]] + 1, hi = pos[E[i]];
while (lo < hi) {
int mid = (lo + hi) / 2;
if (maxquery(pos[S[i]], mid + 1) > R[i]) {
hi = mid;
} else {
lo = mid + 1;
}
}
if (minquery(lo - 1, pos[E[i]] + 1) >= L[i]) {
res[i] = 1;
}
}
}
return res;
}
