// ~~ icebear love attttt ~~
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
template<class T>
bool minimize(T &a, const T &b) {
if (a > b) return a = b, true;
return false;
}
template<class T>
bool maximize(T &a, const T &b) {
if (a < b) return a = b, true;
return false;
}
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebearat"
const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 4e5 + 5;
vector<int> initG[N];
class SegmentTree {
private:
int sizeTree;
vector<int> nodes;
int getSum(int id, int l, int r, int u, int v) {
if (l > v || r < u) return 0;
if (u <= l && r <= v) return nodes[id];
int mid = (l + r) >> 1;
return getSum(id << 1, l, mid, u, v) + getSum(id << 1 | 1, mid + 1, r, u, v);
}
public:
SegmentTree(int n = 0): sizeTree(n), nodes(4 * n + 5) {}
void update(int pos, int value) {
int id = 1, l = 1, r = sizeTree;
while(l < r) {
int mid = (l + r) >> 1;
if (pos > mid) id = (id << 1 | 1), l = mid + 1;
else id = (id << 1), r = mid;
}
nodes[id] += value;
while(id) {
id >>= 1;
nodes[id] = nodes[id << 1] + nodes[id << 1 | 1];
}
}
int getSum(int u, int v) {
return getSum(1, 1, sizeTree, u, v);
}
} IT;
struct DSU_tree {
int node;
vector<int> par, value;
vector<vector<int>> G;
DSU_tree(int n = 0): node(n), par(2 * n + 5), value(2 * n + 5), G(2 * n + 5) {
FOR(i, 0, n) par[i] = i;
}
int root(int v) {
return (par[v] == v ? v : par[v] = root(par[v]));
}
void unite(int u, int v) {
int tmp = u;
u = root(u); v = root(v);
if (u == v) return;
node++;
par[u] = par[v] = par[node] = node;
value[node] = tmp;
G[node].pb(u);
G[node].pb(v);
// cout << node << ' ' << u << '\n';
// cout << node << ' ' << v << '\n';
}
} DST_from_S, DST_from_E;
struct Query {
int U, V; // range of second subtree
int id;
Query(int u = 0, int v = 0, int i = 0):
U(u), V(v), id(i) {}
};
vector<Query> del[N], add[N];
int parS[18][N], tinS[N], toutS[N], e_tourS[N], timerS = 0;
int parE[18][N], tinE[N], toutE[N], e_tourE[N], timerE = 0;
void dfs_S(int u) {
tinS[u] = ++timerS;
e_tourS[timerS] = u;
for(int v : DST_from_S.G[u]) {
parS[0][v] = u;
dfs_S(v);
}
toutS[u] = timerS;
}
void dfs_E(int u) {
tinE[u] = ++timerE;
e_tourE[timerE] = u;
for(int v : DST_from_E.G[u]) {
parE[0][v] = u;
dfs_E(v);
}
toutE[u] = timerE;
}
void build_DSUtree_from_S(int N) {
DST_from_S = DSU_tree(N - 1);
RED(i, N) for(int v : initG[i])
if (v > i)
DST_from_S.unite(i, v);
memset(parS, -1, sizeof parS);
dfs_S(DST_from_S.node);
FOR(j, 1, 17) REP(i, DST_from_S.node)
parS[j][i] = parS[j - 1][parS[j - 1][i]];
}
void build_DSUtree_from_E(int N) {
DST_from_E = DSU_tree(N - 1);
REP(i, N) for(int v : initG[i])
if (v < i)
DST_from_E.unite(i, v);
memset(parE, -1, sizeof parE);
dfs_E(DST_from_E.node);
FOR(j, 1, 17) REP(i, DST_from_E.node)
parE[j][i] = parE[j - 1][parE[j - 1][i]];
}
int findRoot_from_S(int u, int lower) { // find node contains component using all nodes >= lower
RED(j, 18) if (parS[j][u] != -1 && DST_from_S.value[parS[j][u]] >= lower)
u = parS[j][u];
return u;
}
int findRoot_from_E(int u, int upper) { // find node contains component with all nodes <= upper
RED(j, 18) if (parE[j][u] != -1 && DST_from_E.value[parE[j][u]] <= upper)
u = parE[j][u];
return u;
}
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 = X.size(), Q = S.size();
REP(i, M) {
initG[X[i]].pb(Y[i]);
initG[Y[i]].pb(X[i]);
}
// cout << "S TREE:\n";
build_DSUtree_from_S(N);
// cout << "E TREE:\n";
build_DSUtree_from_E(N);
REP(i, Q) {
int subtree_S = findRoot_from_S(S[i], L[i]);
int subtree_E = findRoot_from_E(E[i], R[i]);
int L = tinS[subtree_S], R = toutS[subtree_S];
int U = tinE[subtree_E], V = toutE[subtree_E];
// cout << subtree_S << ' ' << L << ' ' << R << '\n';
// cout << subtree_E << ' ' << U << ' ' << V << '\n';
// check if there is a common value in e_tourS[L...R] and e_tourE[U...V]
del[L - 1].emplace_back(U, V, i);
add[R].emplace_back(U, V, i);
}
// REP(i, DST_from_S.node)
// cout << "Node " << i << " : " << tinS[i] << ' ' << toutS[i] << ' ' << tinE[i] << ' ' << toutE[i] << '\n';
vector<int> ans(Q);
IT = SegmentTree(DST_from_S.node);
FOR(i, 1, DST_from_S.node + 1) {
int node = e_tourS[i];
if (node < N) {
IT.update(tinE[node], +1);
}
// sum(L, R) = sum(1, R) - sum(1, L - 1)
for(auto query : del[i]) ans[query.id] -= IT.getSum(query.U, query.V);
for(auto query : add[i]) ans[query.id] += IT.getSum(query.U, query.V);
}
for(int &i : ans) i = min(i, 1);
return ans;
}
// int main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// // vector<int> ans = check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2},
// // {4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
// vector<int> ans = check_validity(10, {6, 1, 8, 2, 9, 2, 8, 6, 3},
// {7, 5, 0, 9, 4, 7, 5, 0, 4}, {4, 8, 1, 8, 8, 0, 9, 1, 9, 9},
// {9, 1, 8, 3, 9, 1, 0, 7, 4, 5}, {0, 8, 1, 5, 3, 0, 6, 1, 5, 0}, {9, 9, 8, 5, 9, 2, 6, 8, 6, 9});
// for(int x : ans) cout << x << ' ';
// return 0;
// }
