#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
template <class F>
struct yc {
F f_;
yc(F &&f) : f_(std::forward<F>(f)) {}
decltype(auto) operator()(auto &&...args) {
return f_(std::ref(*this), std::forward<decltype(args)>(args)...);
}
};
struct krusk {
vector<array<int, 18>> u;
vector<int> l, r, lo, hi;
vector<int> order, where;
vector<int> lm, rm;
krusk(int n, const vector<array<int, 2>> &e)
: u(2 * n - 1),
l(n - 1, -1),
r(n - 1, -1),
lo(2 * n - 1),
hi(2 * n - 1),
where(2 * n - 1, -1),
lm(2 * n - 1, (int)1e9),
rm(2 * n - 1, -(int)1e9) {
vector<int> boss(n, -1), root(n);
iota(root.begin(), root.end(), 0);
iota(lo.begin(), lo.begin() + n, 0);
iota(hi.begin(), hi.begin() + n, 0);
int nxt = n;
auto find = yc([&](auto find, int i) -> int {
if (boss[i] < 0) return i;
return boss[i] = find(boss[i]);
});
auto unite = [&](int i, int j) {
i = find(i), j = find(j);
if (i == j) return false;
if (boss[i] > boss[j]) swap(i, j);
boss[i] += boss[j];
boss[j] = i;
l[nxt - n] = root[i];
r[nxt - n] = root[j];
lo[nxt] = min(lo[root[i]], lo[root[j]]);
hi[nxt] = max(hi[root[i]], hi[root[j]]);
root[i] = nxt;
root[j] = -1;
++nxt;
return true;
};
for (auto [i, j] : e) unite(i, j);
assert(nxt == 2 * n - 1);
order.reserve(2 * n - 1);
auto dfs = yc([&](auto dfs, int i, int p) -> void {
u[i][0] = p;
for (int lvl = 0; lvl + 1 < u[i].size(); ++lvl)
u[i][lvl + 1] = u[u[i][lvl]][lvl];
if (i >= n && l[i - n] >= 0) dfs(l[i - n], i);
where[i] = (int)order.size();
order.push_back(i);
lm[i] = min(lm[i], where[i]);
rm[i] = max(rm[i], where[i]);
if (i >= n && r[i - n] >= 0) dfs(r[i - n], i);
lm[p] = min(lm[p], lm[i]);
rm[p] = max(rm[p], rm[i]);
});
dfs(nxt - 1, nxt - 1);
}
array<int, 2> qry(int i, int mn, int mx) {
assert(mn <= lo[i] && hi[i] <= mx);
for (int lvl = (int)u[i].size() - 1; lvl >= 0; --lvl) {
int j = u[i][lvl];
if (mn <= lo[j] && hi[j] <= mx) i = j;
}
return {lm[i], rm[i]};
}
};
vector<int> check_validity(int n, vector<int> ei, vector<int> ej,
vector<int> starts, vector<int> targets,
vector<int> los, vector<int> his) {
int m = (int)ei.size();
assert((int)ej.size() == m);
vector<array<int, 2>> e(m);
for (int mm = 0; mm < m; ++mm) {
auto &[i, j] = e[mm];
i = ei[mm];
j = ej[mm];
}
sort(e.begin(), e.end(), [&](auto e0, auto e1) {
auto [i0, j0] = e0;
auto [i1, j1] = e1;
return max(i0, j0) < max(i1, j1);
});
auto lo_tree = krusk(n, e);
sort(e.begin(), e.end(), [&](auto e0, auto e1) {
auto [i0, j0] = e0;
auto [i1, j1] = e1;
return min(i0, j0) > min(i1, j1);
});
auto hi_tree = krusk(n, e);
int q = (int)starts.size();
assert(q == (int)targets.size());
assert(q == (int)los.size());
assert(q == (int)his.size());
vector<int> ans(q);
int offset = 1;
while (offset < 2 * n - 1) offset *= 2;
vector<basic_string<int>> st(2 * offset);
for (int i = 0; i < n; ++i)
st[offset + hi_tree.where[i]].push_back(lo_tree.where[i]);
for (int I = offset - 1; I; --I)
std::merge(st[2 * I].begin(), st[2 * I].end(), st[2 * I + 1].begin(),
st[2 * I + 1].end(), back_inserter(st[I]));
auto check = [&](const auto &v, int lo, int hi) {
auto it0 = lower_bound(v.begin(), v.end(), lo);
auto it1 = upper_bound(v.begin(), v.end(), hi);
return it0 != it1;
};
auto qry = [&](int i, int j, int x, int y) {
i += offset - 1;
j += offset + 1;
while (i + 1 < j) {
if (i % 2 == 0 && check(st[i + 1], x, y)) return true;
if (j % 2 == 1 && check(st[j - 1], x, y)) return true;
i >>= 1, j >>= 1;
}
return false;
};
for (int qq = 0; qq < q; ++qq) {
int s = starts[qq];
int t = targets[qq];
int lo = los[qq];
int hi = his[qq];
auto [sl, sr] = hi_tree.qry(s, lo, n - 1);
auto [tl, tr] = lo_tree.qry(t, 0, hi);
ans[qq] = qry(sl, sr, tl, tr);
}
return ans;
}
