#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include "werewolf.h"
#include <bits/stdc++.h>
#define ar array
using namespace std;
struct reachability_tree {
vector<int> boss, under, tup, time_of, lk, rk, leftmost, rightmost;
vector<int> up[20];
int find(int i) {
return i == boss[i] ? i : boss[i] = find(boss[i]);
}
void unite(int i, int j) {
i = find(i), j = find(j);
if (i == j) return;
if (under[i] < under[j]) swap(i, j);
under[i] += under[j];
boss[j] = i;
tup[i] = max(tup[i], tup[j]);
}
int nxt_new_node;
void add_edge(int i, int j, int t) {
i = find(i), j = find(j);
if (i == j) return;
i = tup[i];
j = tup[j];
lk[nxt_new_node] = i;
rk[nxt_new_node] = j;
time_of[nxt_new_node] = t;
unite(i, nxt_new_node);
unite(j, nxt_new_node);
++nxt_new_node;
}
vector<int> tour, pof;
void dfs(int cur) {
if (lk[cur] != -1) {
dfs(lk[cur]);
leftmost[cur] = leftmost[lk[cur]];
up[0][lk[cur]] = cur;
} else leftmost[cur] = tour.size();
pof[cur] = tour.size();
tour.push_back(cur);
up[0][cur] = cur;
if (rk[cur] != -1) {
dfs(rk[cur]);
rightmost[cur] = rightmost[rk[cur]];
up[0][rk[cur]] = cur;
} else rightmost[cur] = tour.size()-1;
}
ar<int, 2> qry(int i, int t) {
for (int lvl = 19; lvl >= 0; --lvl)
if (time_of[up[lvl][i]] <= t)
i = up[lvl][i];
return {leftmost[i], rightmost[i]};
}
reachability_tree(int n, vector<ar<int, 3>> e) {
boss.resize(2*n);
under.resize(2*n, 1);
tup.resize(2*n);
time_of.resize(2*n);
lk.resize(2*n, -1);
rk.resize(2*n, -1);
pof.resize(2*n, -1);
rightmost.resize(2*n, -1);
leftmost.resize(2*n, -1);
iota(boss.begin(), boss.end(), 0);
iota(tup.begin(), tup.end(), 0);
nxt_new_node = n;
for (auto [w, i, j] : e)
add_edge(i, j, w);
for (int lvl = 0; lvl < 20; ++lvl) {
up[lvl].resize(2*n);
iota(up[lvl].begin(), up[lvl].end(), 0);
}
for (int i = 0; i < 2*n; ++i)
if (i == find(i))
dfs(tup[i]);
for (int lvl = 0; lvl < 19; ++lvl)
for (int i = 0; i < 2*n; ++i)
up[lvl+1][i] = up[lvl][up[lvl][i]];
/*cout << "tour: ";
for (int x : tour)
cerr << x << ' ';
cerr << '\n';
cout << "pof: ";
for (int x : pof)
cerr << x << ' ';
cerr << '\n';
cout << "leftmost: ";
for (int l : leftmost)
cerr << l << ' ';
cerr << '\n';
cout << "rightmost: ";
for (int r : rightmost)
cerr << r << ' ';
cerr << '\n';*/
}
};
const int mxN = 4e5;
const int lg2 = __lg(mxN-1)+1;
const int offset = 1<<lg2;
vector<int> values[2*offset];
void insert(int i, int j) {
i += offset;
do {
values[i].push_back(j);
} while (i /= 2);
}
bool check(int I, int lo, int hi) {
return lower_bound(values[I].begin(), values[I].end(), lo)
!= upper_bound(values[I].begin(), values[I].end(), hi);
}
bool qry(int li, int hi, int lj, int hj) {
li += offset-1;
hi += offset+1;
while (li+1 < hi) {
if (li%2 == 0) if (check(li+1, lj, hj)) return true;
if (hi%2 == 1) if (check(hi-1, lj, hj)) return true;
li /= 2, hi /= 2;
}
return false;
}
vector<int> check_validity(int n, vector<int> e0, vector<int> e1,
vector<int> q0, vector<int> q1,
vector<int> ls, vector<int> rs) {
int m = e0.size();
int q = q0.size();
vector<ar<int, 3>> e(m);
for (int mm = 0; mm < m; ++mm)
e[mm] = {max(e0[mm], e1[mm]), e0[mm], e1[mm]};
sort(e.begin(), e.end());
reachability_tree lo_tree(n, e);
for (auto &[w, i, j] : e)
w = n-min(i, j);
sort(e.begin(), e.end());
reachability_tree hi_tree(n, e);
for (int nn = 0; nn < n; ++nn) {
int i = lo_tree.pof[nn];
int j = hi_tree.pof[nn];
insert(i, j);
}
for (int i = 2*offset-1; i > 0; --i)
sort(values[i].begin(), values[i].end());
vector<int> ans(q);
for (int i = 0; i < q; ++i) {
//cerr << '\n';
//cerr << q0[i] << ' ' << q1[i] << ' ' << ls[i] << ' ' << rs[i] << '\n';
auto [ll, lr] = lo_tree.qry(q1[i], rs[i]);
auto [hl, hr] = hi_tree.qry(q0[i], n-ls[i]);
ans[i] = qry(ll, lr, hl, hr);
}
return ans;
}
