#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
struct query {
int from, to, l, r, idx;
};
int n, m, q, dfs_cnt;
vector< vector<int> > g, g2;
vector<query> queries;
vector<int> ans, p, ord_l, ord_r;
vector< pair<int, int> > range;
int root(int u) {
if (p[u] == -1) return u;
return p[u] = root(p[u]);
}
int connect(int u, int v) {
u = root(u); v = root(v);
if (u == v) return u;
p[v] = p[u] = (int) p.size();
p.push_back(-1);
g2.push_back({u, v});
return (int) p.size() - 1;
}
pair<int, int> dfs(int u, bool phase) {
if (g2[u].empty()) {
if (phase) ord_l[u] = dfs_cnt++;
else ord_r[u] = dfs_cnt++;
return range[u] = {dfs_cnt - 1, dfs_cnt - 1};
}
range[u] = {INF, -INF};
for (auto &v : g2[u]) {
int l, r;
tie(l, r) = dfs(v, phase);
range[u].first = min(range[u].first, l);
range[u].second = max(range[u].second, r);
}
return range[u];
}
struct node {
int l, r, val;
node *left, *right;
};
node *build(int l, int r) {
if (l == r) return new node{l, r, -INF, nullptr, nullptr};
node *left = build(l, (l + r) / 2), *right = build((l + r) / 2 + 1, r);
return new node{l, r, -INF, left, right};
}
void update(node *cur, int idx, int v) {
if (cur->l == cur->r) {
cur->val = v;
return;
}
if (idx <= cur->left->r) update(cur->left, idx, v);
else update(cur->right, idx, v);
cur->val = max(cur->left->val, cur->right->val);
}
int query_max(node *cur, int l, int r) {
if (cur->l > r || cur->r < l) return -INF;
if (l <= cur->l && cur->r <= r) return cur->val;
return max(query_max(cur->left, l, r), query_max(cur->right, l, r));
}
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 = (int) X.size(); q = (int) S.size();
g.resize(n);
for (int i = 0; i < m; i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
vector<int> rep_l(q + 1), rep_r(q + 1);
vector< pair<int, int> > range_l(q + 1), range_r(q + 1);
for (int i = 0; i < q; i++) queries.push_back({S[i], E[i], L[i], R[i], i});
queries.push_back({0, n - 1, 0, n - 1, q}); q++;
sort(queries.begin(), queries.end(), [](const query &a, const query &b) {
return a.l > b.l;
});
ans.resize(q);
g2.assign(n, vector<int>());
int u = n;
p.assign(n, -1);
vector<bool> used(n, false);
for (auto &[from, to, l, r, idx] : queries) {
while (u > l) {
u--;
used[u] = true;
for (auto &v : g[u]) if (used[v]) connect(u, v);
}
rep_l[idx] = root(from);
}
ord_l.resize((int) p.size());
dfs_cnt = 0;
range.resize((int) p.size());
dfs((int) p.size() - 1, true);
for (auto &[from, to, l, r, idx] : queries) range_l[idx] = range[rep_l[idx]];
sort(queries.begin(), queries.end(), [](const query &a, const query &b) {
return a.r < b.r;
});
ans.resize(q);
g2.assign(n, vector<int>());
u = -1;
p.assign(n, -1);
used.assign(n, false);
for (auto &[from, to, l, r, idx] : queries) {
while (u < r) {
u++;
used[u] = true;
for (auto &v : g[u]) if (used[v]) connect(u, v);
}
rep_r[idx] = root(to);
}
ord_r.resize((int) p.size());
dfs_cnt = 0;
range.resize((int) p.size());
dfs((int) p.size() - 1, false);
for (auto &[from, to, l, r, idx] : queries) range_r[idx] = range[rep_r[idx]];
vector<int> ord(n); iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int a, int b) {
return ord_r[a] < ord_r[b];
});
sort(queries.begin(), queries.end(), [&](const query &a, const query &b) {
return range_r[a.idx].second < range_r[b.idx].second;
});
u = -1;
node *root = build(0, n - 1);
for (auto &[from, to, l, r, idx] : queries) {
while (u < range_r[idx].second) {
u++;
update(root, ord_l[ord[u]], ord_r[ord[u]]);
}
ans[idx] = query_max(root, range_l[idx].first, range_l[idx].second) >= range_r[idx].first;
}
ans.pop_back();
return move(ans);
}
