#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int N = 200'000 + 10;
vector<int> ad[N];
int a[N], rvs[N], it;
void dfs(int u, int p = -1) {
a[it] = u; rvs[u] = it++;
for (const auto& v : ad[u]) if (v != p) dfs(v, u);
}
int g[N << 2][2];
void build(int s, int l, int r) {
if (l == r) {
g[s][0] = g[s][1] = a[l];
return;
}
int mid = l + r >> 1;
build(s << 1, l, mid); build(s << 1 | 1, mid + 1, r);
g[s][0] = min(g[s << 1][0], g[s << 1 | 1][0]);
g[s][1] = max(g[s << 1][1], g[s << 1 | 1][1]);
}
int getmi(int s, int l, int r, int u, int v) {
if (v < l || u > r) return 200'000;
if (u <= l && r <= v) return g[s][0];
int mid = l + r >> 1;
return min(getmi(s << 1, l, mid, u, v), getmi(s << 1 | 1, mid + 1, r, u, v));
}
int getma(int s, int l, int r, int u, int v) {
if (v < l || u > r) return -1;
if (u <= l && r <= v) return g[s][1];
int mid = l + r >> 1;
return max(getma(s << 1, l, mid, u, v), getma(s << 1 | 1, mid + 1, r, u, v));
}
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(), q = s.size();
bool line = true;
for (int i = 0; i < m; ++i) {
int u = x[i], v = y[i];
ad[u].push_back(v);
ad[v].push_back(u);
line &= (ad[u].size() <= 2 && ad[v].size() <= 2);
}
if (n <= 3000 && m <= 6000 && q <= 3000) {
vector<int> answer;
for (int i = 0; i < q; ++i) {
vector<vector<int>> f(n, vector<int>(2));
vector<int> mk(n);
for (int j = 0; j < n; ++j) mk[j] = (j < l[i] ? 0 : j <= r[i] ? 1 : 2);
queue<int> que;
f[s[i]][0] = f[s[i]][mk[s[i]] == 1] = true;
que.push(s[i]);
while (que.size()) {
auto u = que.front(); que.pop();
for (const auto& v : ad[u]) {
if (f[v][0] && f[v][1]) continue;
pair<int, int> pre = {f[v][0], f[v][1]};
if (mk[v] >= 1) f[v][0] |= f[u][0];
if (mk[v] <= 1) f[v][1] |= (f[u][1] || mk[v] == 1);
if (make_pair(f[v][0], f[v][1]) != pre) que.push(v);
}
}
answer.push_back(f[e[i]][1]);
}
return answer;
}
if (line) {
int root;
for (int i = 0; i < n; ++i) if (ad[i].size() == 1) root = i;
dfs(root);
build(1, 0, n - 1);
vector<int> answer;
for (int i = 0; i < q; ++i) {
if (rvs[s[i]] < rvs[e[i]]) {
int st = rvs[s[i]], ed = rvs[e[i]];
int vegan = -1;
{
int lt = st, rt = ed;
while (lt <= rt) {
int mid = lt + rt >> 1;
if (getma(1, 0, n - 1, mid, ed) > r[i]) lt = (vegan = mid) + 1;
else rt = mid - 1;
}
}
int meat = -1;
{
int lt = st, rt = ed;
while (lt <= rt) {
int mid = lt + rt >> 1;
if (getmi(1, 0, n - 1, st, mid) < l[i]) rt = (meat = mid) - 1;
else lt = mid + 1;
}
}
if (meat == -1 || vegan == -1) {
answer.push_back(1);
continue;
}
if (meat <= vegan + 1) answer.push_back(0);
else answer.push_back(1);
} else {
int st = rvs[e[i]], ed = rvs[s[i]];
int vegan = -1;
{
int lt = st, rt = ed;
while (lt <= rt) {
int mid = lt + rt >> 1;
if (getma(1, 0, n - 1, st, mid) > r[i]) rt = (vegan = mid) - 1;
else lt = mid + 1;
}
}
int meat = -1;
{
int lt = st, rt = ed;
while (lt <= rt) {
int mid = lt + rt >> 1;
if (getmi(1, 0, n - 1, mid, ed) < l[i]) lt = (meat = mid) + 1;
else rt = mid - 1;;
}
}
if (meat == -1 || vegan == -1) {
answer.push_back(1);
continue;
}
if (meat >= vegan - 1) answer.push_back(0);
else answer.push_back(1);
}
}
return answer;
}
}
