#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
struct Segtree {
int n;
vi ma, mi;
Segtree (vi ord) {
n = ord.size();
ma.resize(4 * n);
mi.resize(4 * n);
build(1, 0, n, ord);
}
void build (int i, int sl, int sr, vi &ord) {
if (sr - sl == 1) {
mi[i] = ma[i] = ord[sl];
return;
}
int mid = sl + sr >> 1;
build(2 * i, sl, mid, ord);
build(2 * i + 1, mid, sr, ord);
mi[i] = min(mi[2 * i], mi[2 * i + 1]);
ma[i] = max(ma[2 * i], ma[2 * i + 1]);
}
int getL (int i, int sl, int sr, int l, int t) {
if (sr <= l) return n;
if (mi[i] >= t) return n;
if (sr - sl == 1) return sl;
int mid = sl + sr >> 1;
int ans = getL(2 * i, sl, mid, l, t);
if (ans != n) return ans;
return getL(2 * i + 1, mid, sr, l, t);
}
int getL (int i, int l) {
return getL(1, 0, n, i, l);
}
int getR (int i, int sl, int sr, int r, int t) {
if (sl >= r) return -1;
if (ma[i] <= t) return -1;
if (sr - sl == 1) return sl;
int mid = sl + sr >> 1;
int ans = getR(2 * i + 1, mid, sr, r, t);
if (ans != -1) return ans;
return getR(2 * i, sl, mid, r, t);
}
int getR (int i, int r) {
return getR(1, 0, n, i, r);
}
};
vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
int q = s.size();
int m = x.size();
vector<vi> adj(n);
for (int i = 0; i < m; i++) {
adj[x[i]].push_back(y[i]);
adj[y[i]].push_back(x[i]);
}
vi ans(q);
vi ord(n), pos(n);
for (int i = 0; i < n; i++) {
if (adj[i].size() == 1) {
ord[0] = i;
ord[1] = adj[i][0];
pos[i] = 0;
pos[adj[i][0]] = 1;
break;
}
}
for (int i = 1; i + 1 < n; i++) {
int j = adj[ord[i]][0] ^ adj[ord[i]][1] ^ ord[i - 1];
ord[i + 1] = j;
pos[j] = i + 1;
}
vi rev_ord = ord; reverse(rev_ord.begin(), rev_ord.end());
vi rev_pos(n);
for (int i = 0; i < n; i++) rev_pos[rev_ord[i]] = i;
Segtree Ord(ord);
Segtree Rev(rev_ord);
for (int i = 0; i < q; i++) {
int left, right;
if (pos[s[i]] < pos[e[i]]) {
left = Ord.getL(pos[s[i]], l[i]) - 1;
right = Ord.getR(pos[e[i]], r[i]) + 1;
} else {
left = Rev.getL(rev_pos[s[i]], l[i]) - 1;
right = Rev.getR(rev_pos[e[i]], r[i]) + 1;
}
ans[i] = left >= right;
}
return ans;
}
