#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pll;
#define all(x) (x).begin(), (x).end()
#define X first
#define Y second
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const int MAXN = 1e6 + 10;
const int LOG = 20;
int n, m, q;
namespace DSU_L {
int C[MAXN], F[MAXN], par[MAXN][LOG], sz, T[MAXN], dfs_time, tin[MAXN], tout[MAXN];
vector<int> adj[MAXN];
inline void init() {
sz = n - 1;
T[0] = -1;
for (int i = 0; i < n; i++) {
F[i] = C[i] = i;
T[i] = MAXN;
}
}
inline int find(int v) {
return C[v] == v ? v : C[v] = find(C[v]);
}
inline bool unite(int u, int v, int l) {
u = find(u), v = find(v);
if (u == v) return false;
int fu = F[u], fv = F[v];
sz++;
par[fu][0] = sz;
par[fv][0] = sz;
C[v] = u;
T[sz] = l;
F[u] = sz;
adj[sz].push_back(fu);
adj[sz].push_back(fv);
return true;
}
void dfs(int v) {
tin[v] = ++dfs_time;
for (int u : adj[v])
dfs(u);
tout[v] = dfs_time;
}
inline void init_tree() {
dfs(sz);
par[sz][0] = sz;
for (int i = 1; i < LOG; i++)
for (int v = 0; v <= sz; v++)
par[v][i] = par[par[v][i - 1]][i - 1];
}
inline int max_node(int v, int l) {
for (int i = LOG - 1; i >= 0; i--)
if (T[par[v][i]] >= l)
v = par[v][i];
return v;
}
inline pll get_seg(int v, int l) {
v = max_node(v, l);
return {tin[v], tout[v]};
}
}
namespace DSU_R {
int par[MAXN];
vector<int> C[MAXN];
set<int> st[MAXN];
inline void init() {
for (int i = 0; i < n; i++) {
st[i].insert(DSU_L::tin[i]);
par[i] = i;
C[i].push_back(i);
}
}
inline bool unite(int u, int v) {
u = par[u], v = par[v];
if (u == v) return false;
if (C[u].size() < C[v].size()) swap(u, v);
for (int e : C[v]) {
C[u].push_back(e);
par[e] = u;
}
for (int e : st[v])
st[u].insert(e);
C[v].clear();
st[v].clear();
return true;
}
inline bool get(int v, int l, int r) {
v = par[v];
auto it = st[v].lower_bound(l);
return it != st[v].end() && *it <= r;
}
}
vector<int> ans, adj[MAXN], QR[MAXN];
vector<int> check_validity(int N_, vector<int> X_, vector<int> Y_,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
n = N_;
m = X_.size();
q = S.size();
for (int i = 0; i < m; i++) {
adj[X_[i]].push_back(Y_[i]);
adj[Y_[i]].push_back(X_[i]);
}
DSU_L::init();
for (int v = n - 1; v >= 0; v--) {
for (int u : adj[v]) {
if (u < v) continue;
DSU_L::unite(u, v, v);
}
}
DSU_L::init_tree();
DSU_R::init();
for (int i = 0; i < q; i++)
QR[R[i]].push_back(i);
ans.resize(q);
for (int r = 0; r < n; r++) {
for (int u : adj[r]) {
if (u > r) continue;
DSU_R::unite(r, u);
}
for (int i : QR[r]) {
auto [tl, tr] = DSU_L::get_seg(S[i], L[i]);
ans[i] = DSU_R::get(E[i], tl, tr);
}
}
return ans;
}
// TODO: fill ans
