#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;
struct Edge {
ll u, v, w;
};
struct DSU {
vll par, sz, nn, bioPar;
vll tin, tout;
ll timer;
ll n;
// vector <vii> qs;
// vll vans;
vii funnyEgs;
vector <vll> adj;
function <ll(ll, ll)> a;
ll newId () {
ll id = par.size();
par.push_back(id);
bioPar.push_back(id);
sz.push_back(1);
adj.push_back(vll({}));
nn.push_back(-15);
tin.push_back(-15);
tout.push_back(-15);
return id;
}
DSU (ll n, function <ll(ll, ll)> a): par(n), sz(n, 1), nn(n), bioPar(n), tin(n, -15), tout(n, -15), timer(0), /* qs(n, vii({})), */ funnyEgs(0), adj(n, vll({})), a(a), n(n) { iota(par.begin(), par.end(), 0); iota(nn.begin(), nn.end(), 0); }
ll find (ll u) { return u == par[u] ? u : par[u] = find(par[u]); }
void join (ll u, ll v) {
// cerr << "at-1\n";
u = find(u);
v = find(v);
if (u == v) return;
// cerr << "at0\n";
ll id = newId();
// cerr << "at1\n";
adj[id].push_back(u);
adj[id].push_back(v);
// cerr << "at2\n";
bioPar[id] = id;
// cerr << "at3\n";
bioPar[u] = par[u] = id;
bioPar[v] = par[v] = id;
// cerr << "at4\n";
nn[id] = a(nn[u], nn[v]);
// cerr << id << " par of " << u << ' ' << v << '\n';
// cerr << "at5\n";
// if (qs[u].size() > qs[v].size()) swap(u, v);
// for (auto [vth, qid] : qs[u]) {
// if (find(vth) == v) {
// vans[qid] = id;
// } else qs[v].push_back({ vth, qid });
// }
}
ll findRoot (ll u, ll x) {
if (bioPar[u] == u) return u;
if (a(nn[bioPar[u]], x) == x) return findRoot(bioPar[u], x);
return u;
}
vll doDfs (ll u, ll x) {
ll ahm = findRoot(u, x);
vll ans;
dfs(ahm, ans);
return ans;
}
ii getRange (ll u, ll x) {
ll ahm = findRoot(u, x);
return { tin[ahm], tout[ahm] };
}
void dfs (ll u, vll &sub) {
tin[u] = timer;
if (u < n) timer++;
// cerr << nn[u] << ' ';
assert(adj[u].empty() == (u < n));
if (adj[u].empty()) sub.push_back(u);
for (ll v : adj[u]) {
dfs(v, sub);
// cerr << nn[u] << ' ';
}
tout[u] = timer-1;
}
// void addQ (ll u, ll v, ll qid) {
// assert(qid == vans.size());
// qs[u].push_back({ v, qid });
// qs[v].push_back({ u, qid });
// vans.push_back(-15);
// }
};
struct SegTree {
vector <vll> tree;
// vll tree;
ll n;
SegTree (ll n): tree(2*n, vll({})), n(n) {}
// SegTree (ll n): tree(n, -15), n(n) {}
void update (ll id, ll val) {
for (id += n; id > 0; id >>= 1)
tree[id].push_back(val);
}
// void update (ll id, ll val) {
// tree[id] = val;
// }
void build () {
for (ll id = 0; id < 2*n; id++)
sort(tree[id].begin(), tree[id].end());
}
// bool query (ll ql, ll qr, ll l, ll r) {
// bool ans = false;
// for (ll i = ql; i <= qr; i++)
// ans |= l <= tree[i] && tree[i] <= r;
// return ans;
// }
bool query (ll ql, ll qr, ll l, ll r) {
bool ans = false;
for (ql += n, qr += n+1; ql < qr; ql >>= 1, qr >>= 1) {
if (ql&1) { ans |= upper_bound(tree[ql].begin(), tree[ql].end(), r) - lower_bound(tree[ql].begin(), tree[ql].end(), l); ql++; }
if (qr&1) { --qr; ans |= upper_bound(tree[qr].begin(), tree[qr].end(), r) - lower_bound(tree[qr].begin(), tree[qr].end(), l); }
}
return ans;
}
};
vi check_validity (int n, vi us, vi vs, vi s, vi e, vi vl, vi vr) {
ll Q = s.size();
vector <Edge> egsMn, egsMx;
for (ll i = 0; i < us.size(); i++) {
// adj[us[i]].push_back(vs[i]);
// adj[vs[i]].push_back(us[i]);
egsMn.push_back({ us[i], vs[i], min(us[i], vs[i]) });
egsMx.push_back({ us[i], vs[i], max(us[i], vs[i]) });
}
sort(egsMn.begin(), egsMn.end(), [&](Edge a, Edge b) { return a.w > b.w; });
sort(egsMx.begin(), egsMx.end(), [&](Edge a, Edge b) { return a.w < b.w; });
DSU dsuMn(n, [&](ll a, ll b) { return min(a, b); });
for (auto [u, v, w] : egsMn) {
// cerr << u << ' ' << v << ' ' << w << '\n';
// cerr << "joining\n";
dsuMn.join(u, v);
// cerr << "joiningee\n";
}
DSU dsuMx(n, [&](ll a, ll b) { return max(a, b); });
for (auto [u, v, w] : egsMx) {
// cerr << u << ' ' << v << ' ' << w << '\n';
// cerr << "joining\n";
dsuMx.join(u, v);
// cerr << "joiningee\n";
}
vll ordMn, ordMx;
dsuMn.dfs(dsuMn.par.size()-1, ordMn);
dsuMx.dfs(dsuMx.par.size()-1, ordMx);
SegTree st(n);
for (ll u = 0; u < n; u++)
st.update(dsuMx.tin[u], dsuMn.tin[u]);
st.build();
// cerr << << '\n';
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 ancMn = dsuMn.findRoot(s[qid], vl[qid]);
// ll ancMx = dsuMx.findRoot(e[qid], vr[qid]);
// vll accMn = dsuMn.doDfs(s[qid], vl[qid]);
// vll accMx = dsuMx.doDfs(e[qid], vr[qid]);
auto [lMn, rMn] = dsuMn.getRange(s[qid], vl[qid]);
auto [lMx, rMx] = dsuMx.getRange(e[qid], vr[qid]);
// cerr << lMn << ' ' << rMn << '\n';
// cerr << lMx << ' ' << rMx << '\n';
// sort(accMn.begin(), accMn.end());
ans[qid] = st.query(lMx, rMx, lMn, rMn);
// for (ll i : accMx) {
// ans[qid] |= binary_search(accMn.begin(), accMn.end(), i);
// }
// for (ll i : accMn) cerr << i << ' '; cerr << '\n';
// for (ll i : accMx) cerr << i << ' '; cerr << '\n';
}
// cerr << "ANS DONE\n";
return ans;
}
