#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
struct dsu {
vector<int> p;
dsu() = default;
dsu(int n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
int get(int a) {
return a == p[a] ? a : p[a] = get(p[a]);
}
bool mrg(int a, int b) {
a = get(a);
b = get(b);
if (a == b) {
return false;
}
p[b] = a;
return true;
}
bool same(int a, int b) {
return get(a) == get(b);
}
};
struct SegTree {
int sz = 1;
vector<vector<int>> t;
SegTree() = default;
SegTree(const vector<int> &a) {
int n = (int) a.size();
sz = 1;
while (sz < n) sz <<= 1;
t.assign(sz << 1, {});
for (int i = 0; i < n; ++i) {
t[i + sz] = {a[i]};
}
for (int i = sz - 1; i > 0; --i) {
t[i].resize(t[i << 1].size() + t[i << 1 | 1].size());
merge(t[i << 1].begin(), t[i << 1].end(), t[i << 1 | 1].begin(), t[i << 1 | 1].end(), t[i].begin());
}
}
int get(int l, int r, int val, int x, int lx, int rx) {
if (l >= rx || lx >= r) return inf;
if (l <= lx && rx <= r) {
auto it = lower_bound(t[x].begin(), t[x].end(), val);
if (it == t[x].end()) {
return inf;
} else {
return *it;
}
}
int m = (lx + rx) >> 1;
return min(get(l, r, val, x << 1, lx, m), get(l, r, val, x << 1 | 1, m, rx));
}
};
namespace Werewolf {
const int N = 600000, logn = 20;
int jump[logn][N], weight[N], tin[N], tout[N], T = 0;
vector<int> g[N], ord;
int n, m;
void init(vector<array<int, 3>> e, int _n) {
n = _n;
m = (int)e.size();
dsu d(n + m);
int last = n;
assert(*max_element(tin, tin + N) == 0);
for (auto [w, a, b] : e) {
if (d.same(a, b)) {
g[last].push_back(d.get(a));
d.mrg(last, a);
} else {
g[last].push_back(d.get(a));
g[last].push_back(d.get(b));
d.mrg(last, a);
d.mrg(last, b);
}
weight[last - n] = w;
last += 1;
}
function<void(int)> dfs = [&](int v) {
tin[v] = T;
if (v < n) {
ord.push_back(v);
T++;
}
for (int to : g[v]) {
jump[0][to] = v;
dfs(to);
}
tout[v] = T;
};
memset(tin, -1, sizeof(tin));
for (int i = last - 1; i > -1; --i) {
if (tin[i] == -1) {
jump[0][i] = i;
dfs(i);
}
}
for (int j = 1; j < logn; ++j) {
for (int i = 0; i < n + m; ++i) {
jump[j][i] = jump[j - 1][jump[j - 1][i]];
}
}
}
pair<int, int> get(int v, int w) {
for (int j = logn - 1; j > -1; --j) {
if (weight[jump[j][v] - n] <= w) {
v = jump[j][v];
}
}
return {tin[v], tout[v]};
}
};
namespace Human {
const int N = 600000, logn = 20;
int jump[logn][N], weight[N], tin[N], tout[N], T = 0;
vector<int> g[N], ord;
int n, m;
void init(vector<array<int, 3>> e, int _n) {
n = _n;
m = (int)e.size();
dsu d(n + m);
int last = n;
assert(*max_element(tin, tin + N) == 0);
for (auto [w, a, b] : e) {
if (d.same(a, b)) {
g[last].push_back(d.get(a));
d.mrg(last, a);
} else {
g[last].push_back(d.get(a));
g[last].push_back(d.get(b));
d.mrg(last, a);
d.mrg(last, b);
}
weight[last - n] = w;
last += 1;
}
function<void(int)> dfs = [&](int v) {
tin[v] = T;
if (v < n) {
ord.push_back(v);
T++;
}
for (int to : g[v]) {
jump[0][to] = v;
dfs(to);
}
tout[v] = T;
};
memset(tin, -1, sizeof(tin));
for (int i = last - 1; i > -1; --i) {
if (tin[i] == -1) {
jump[0][i] = i;
dfs(i);
}
}
for (int j = 1; j < logn; ++j) {
for (int i = 0; i < n + m; ++i) {
jump[j][i] = jump[j - 1][jump[j - 1][i]];
}
}
}
pair<int, int> get(int v, int w) {
for (int j = logn - 1; j > -1; --j) {
if (weight[jump[j][v] - n] >= w) {
v = jump[j][v];
}
}
return {tin[v], tout[v]};
}
} //human
vector<int>
check_validity(int n, vector<int> X, vector<int> Y, vector<int> s, vector<int> e, vector<int> L, vector<int> R) {
int m = (int)X.size(), q = (int)e.size();
vector<array<int, 3>> eWerewolf(m), eHuman(m);
for (int i = 0; i < m; ++i) {
if (X[i] > Y[i]) {
swap(X[i], Y[i]);
}
eWerewolf[i] = {Y[i], X[i], Y[i]};
eHuman[i] = {X[i], X[i], Y[i]};
}
sort(eHuman.begin(), eHuman.end(), greater());
sort(eWerewolf.begin(), eWerewolf.end());
Werewolf::init(eWerewolf, n);
Human::init(eHuman, n);
vector<int> a(n);
for (int i = 0; i < n; ++i) {
a[i] = Human::tin[Werewolf::ord[i]];
}
SegTree st(a);
vector<int> ans(q);
for (int i = 0; i < q; ++i) {
auto [hL, hR] = Human::get(s[i], L[i]);
auto [wL, wR] = Werewolf::get(e[i], R[i]);
int x = st.get(wL, wR, hL, 1, 0, st.sz);
ans[i] = (x < hR);
}
return ans;
}
