#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
using ii = pair<int, int>;
using vi = vector<int>;
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
struct DSU {
vi par;
vector<vi> adj;
DSU(int n) : par(n), adj(n) {
iota(all(par), 0);
}
int find(int x) {
if (par[x] == x) return x;
return par[x] = find(par[x]);
}
void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
int p = sz(par);
par[x] = p, par[y] = p;
par.pb(p);
adj.eb();
adj.back().pb(x);
adj.back().pb(y);
}
};
void dfs(int u, vector<vi> &adj, vi &low, vi &high, int &t) {
low[u] = t++;
for (int v : adj[u]) {
dfs(v, adj, low, high, t);
}
high[u] = t;
}
struct FTree {
int n;
vi ft;
FTree(int _n) : n(_n + 9), ft(n, 0) {}
void update(int p) {
for (++p; p < n; p += p & -p) ft[p]++;
}
int get(int p) {
int s = 0;
for (; p > 0; p -= p & -p) s += ft[p];
return s;
}
int query(int l, int r) {
return get(r) - get(l);
}
};
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
int M = sz(X), Q = sz(S);
vector<vi> edgesByMin(N), edgesByMax(N);
forn(i, M) edgesByMin[min(X[i], Y[i])].pb(i);
forn(i, M) edgesByMax[max(X[i], Y[i])].pb(i);
vector<vi> queriesByL(N), queriesByR(N);
forn(i, Q) queriesByL[L[i]].pb(i);
forn(i, Q) queriesByR[R[i]].pb(i);
DSU left(N), right(N);
vi parentL(Q), parentR(Q);
dforn(l, N) {
for (int i : edgesByMin[l]) {
left.unite(X[i], Y[i]);
}
for (int i : queriesByL[l]) {
parentL[i] = left.find(S[i]);
}
}
forn(r, N) {
for (int i : edgesByMax[r]) {
right.unite(X[i], Y[i]);
}
for (int i : queriesByR[r]) {
parentR[i] = right.find(E[i]);
}
}
vi lowL(2 * N - 1), highL(2 * N - 1);
vi lowR(2 * N - 1), highR(2 * N - 1);
int tL = 0, tR = 0;
dfs(left.find(0), left.adj, lowL, highL, tL);
dfs(right.find(0), right.adj, lowR, highR, tR);
vector<vi> toAdd(2 * N);
forn(i, N) toAdd[lowL[i]].pb(lowR[i]);
vector<vector<pair<ii, int>>> queries(2 * N);
forn(i, Q) {
ii range = {lowR[parentR[i]], highR[parentR[i]]};
queries[lowL[parentL[i]]].eb(range, -i - 1);
queries[highL[parentL[i]]].eb(range, i + 1);
}
FTree ft(2 * N);
vi ret(Q, 0);
forn(curr, 2 * N) {
for (auto [range, data] : queries[curr]) {
int type = data < 0 ? -1 : 1;
int id = abs(data) - 1;
auto [l, r] = range;
ret[id] += type * ft.query(l, r);
}
for (int i : toAdd[curr]) ft.update(i);
}
forn(i, Q) {
assert(ret[i] >= 0);
if (ret[i] > 0) ret[i] = 1;
}
return ret;
}
