#include "werewolf.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return l + rd() % (r - l + 1);
}
const int N = 4e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
struct DSU {
int n,node,timer;
vector <int> par;
vector <int> tin,tout;
vector <vector <int>> adj;
DSU(int _n = 0) {
n = _n;
par.assign(2 * n + 5, -1);
adj.resize(2 * n + 5);
tin.assign(2 * n + 5, 0);
tout.assign(2 * n + 5, 0);
node = n;
}
int getpar(int u) {
return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
}
void join(int u, int v) {
u = getpar(u);
v = getpar(v);
if (par[u] > par[v])
swap(u, v);
if (u == v)
return;
adj[node].push_back(u);
adj[node].push_back(v);
par[u] = par[v] = node;
node++;
}
void dfs(int u) {
// cerr << "dfs " << u << " " << timer << "\n";
if (u < n)
tin[u] = ++timer;
for (int v : adj[u]) {
dfs(v);
if (!tin[u])
tin[u] = tin[v];
}
tout[u] = timer;
}
void build() {
timer = 0;
dfs(node - 1);
for (int i = 0; i < node; i++)
par[i] = -1;
node = n;
}
pair <int, int> gettree(int u) {
// cerr << "get tree " << u << " ";
u = getpar(u);
// cerr << u << " " << tin[u] << " " << tout[u] << "\n";
return mp(tin[u], tout[u]);
}
};
DSU pre, suf;
vector <int> st[N << 2];
vector <int> ed[N];
vector <int> qr[N];
pair <int, int> range[N][2];
int tin[N][2];
int ans[N];
int x[N];
int y[N];
int s[N];
int t[N];
int l[N];
int r[N];
int n,m,q;
void update(int id, int l, int r, int pos, int val) {
if (l > pos || r < pos)
return;
st[id].push_back(val);
if (l == r)
return;
int mid = (l + r) >> 1;
update(id << 1, l, mid, pos, val);
update(id << 1 | 1, mid + 1, r, pos, val);
}
void update(int pos, int val) {
update(1, 1, n, pos, val);
}
int getans(int id, int l, int r, int u, int v, int x, int y) {
if (l > v || r < u)
return 0;
if (l >= u && r <= v) {
auto it = lower_bound(ALL(st[id]), x);
return (it != st[id].end() && *it <= y);
}
int mid = (l + r) >> 1;
int lnode = getans(id << 1, l, mid, u, v, x, y);
int rnode = getans(id << 1 | 1, mid + 1, r, u, v, x, y);
return lnode | rnode;
}
int getans(int l, int r, int x, int y) {
return getans(1, 1, n, l, r, x, y);
}
void build() {
pre = suf = DSU(n);
for (int i = 0; i < m; i++)
if (x[i] > y[i])
swap(x[i], y[i]);
for (int i = 0; i < m; i++)
ed[y[i]].push_back(x[i]);
for (int i = 0; i < q; i++)
qr[r[i]].push_back(i);
for (int i = 0; i < n; i++)
for (int j : ed[i])
pre.join(i, j);
pre.build();
for (int i = 0; i < n; i++) {
for (int j : ed[i])
pre.join(i, j);
for (int ind : qr[i])
range[ind][0] = pre.gettree(t[ind]);
}
for (int i = 0; i < n; i++)
tin[i][0] = pre.tin[i];
// process suffix
for (int i = 0; i < n; i++)
qr[i].clear(), ed[i].clear();
for (int i = 0; i < m; i++)
ed[x[i]].push_back(y[i]);
for (int i = 0; i < q; i++)
qr[l[i]].push_back(i);
for (int i = n - 1; i >= 0; i--)
for (int j : ed[i])
suf.join(i, j);
suf.build();
for (int i = n - 1; i >= 0; i--) {
for (int j : ed[i])
suf.join(i, j);
for (int ind : qr[i])
range[ind][1] = suf.gettree(s[ind]);
}
for (int i = 0; i < n; i++)
tin[i][1] = suf.tin[i];
}
void solve() {
for (int i = 0; i < n; i++)
update(tin[i][0], tin[i][1]);
for (int i = 1; i <= 4 * n; i++)
sort(ALL(st[i]));
for (int i = 0; i < q; i++) {
auto [l, r] = range[i][0];
auto [u, v] = range[i][1];
// cerr << l << " " << r << " " << u << " " << v << "\n";
ans[i] = getans(l, r, u, v);
}
}
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();
for (int i = 0; i < m; i++)
x[i] = X[i], y[i] = Y[i];
q = S.size();
for (int i = 0; i < q; i++) {
s[i] = S[i];
t[i] = E[i];
l[i] = L[i];
r[i] = R[i];
}
build();
solve();
vector <int> res;
for (int i = 0; i < q; i++)
res.push_back(ans[i]);
return res;
}
//#include "grader.cpp"
