#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
const ll MAXN = 2E5+16;
const ii IDEM = { MAXN, -MAXN };
vll adj[MAXN];
ll vis[MAXN+MAXN];
ll timer = 1;
ii operator+ (ii a, ii b) {
return {
min(a.first, b.first),
max(a.second, b.second)
};
}
struct SegTree {
vii tree;
ll n;
SegTree (ll n): tree(2*n, IDEM), n(n) {}
void update (ll id, ll val) {
for (tree[id += n] = { val, val }; id > 1; id >>= 1)
tree[id>>1] = tree[id] + tree[id^1];
}
ii query (ll ql, ll qr) {
ii ans = IDEM;
for (ql += n, qr += n+1; ql < qr; ql >>= 1, qr >>= 1) {
if (ql&1) ans = ans + tree[ql++];
if (qr&1) ans = ans + tree[--qr];
}
return ans;
}
};
vi check_validity (int n, vi us, vi vs, vi s, vi e, vi vl, vi vr) {
ll Q = s.size();
for (ll i = 0; i < us.size(); i++) {
adj[us[i]].push_back(vs[i]);
adj[vs[i]].push_back(us[i]);
}
vll ve;
function <void(ll, ll)> dfs = [&](ll u, ll par) {
ve.push_back(u);
for (ll v : adj[u]) {
if (v == par) continue;
dfs(v, u);
}
};
for (ll u = 0; u < n; u++) {
if (adj[u].size() == 2) continue;
assert(adj[u].size() == 1);
dfs(u, u);
break;
}
assert(ve.size() == n);
vll wh(n, -15);
for (ll i = 0; i < n; i++) wh[ve[i]] = i;
SegTree st(n);
for (ll i = 0; i < n; i++) st.update(i, ve[i]);
vi ans(Q, -15);
for (ll qid = 0; qid < Q; qid++) {
assert(vl[qid] <= s[qid]);
assert(e[qid] <= vr[qid]);
assert(vl[qid] <= vr[qid]);
assert(e[qid] != s[qid]);
ll l1 = wh[s[qid]], r1 = wh[s[qid]];
ll l2 = wh[e[qid]], r2 = wh[e[qid]];
{ll l = -1;
while (l+1 < l1) {
ll mid = (l+l1)>>1;
if (st.query(mid, r1).first >= vl[qid])
l1 = mid;
else
l = mid;
}}
assert(st.query(l1, r1).first >= vl[qid]);
{ll r = n;
while (r1+1 < r) {
ll mid = (r1+r)>>1;
if (st.query(l1, mid).first >= vl[qid])
r1 = mid;
else
r = mid;
}}
assert(st.query(l1, r1).first >= vl[qid]);
{ll l = -1;
while (l+1 < l2) {
ll mid = (l+l2)>>1;
if (st.query(mid, r2).second <= vr[qid])
l2 = mid;
else
l = mid;
}}
assert(st.query(l2, r2).second <= vr[qid]);
{ll r = n;
while (r2+1 < r) {
ll mid = (r2+r)>>1;
if (st.query(l2, mid).second <= vr[qid])
r2 = mid;
else
r = mid;
}}
assert(st.query(l2, r2).second <= vr[qid]);
ans[qid] = 1;
if (r1 < l2) ans[qid] = 0;
if (r2 < l1) ans[qid] = 0;
}
return ans;
}
