#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;
const int mxn = 2e5 + 5;
int n;
vector<int> g[mxn];
int num[mxn];
int denum[mxn];
int good[mxn];
int root[mxn], sz[mxn];
vector<int> compv[mxn];
vector<vector<int>> ranges[mxn];
vector<pair<int, int>> roots[mxn];
set<int> comps[mxn];
vector<int> add(int v) {
good[v] = 1;
vector<int> rtn;
for (const auto &i : g[v])
if (good[i])
rtn.push_back(i);
return rtn;
}
void numerate() {
vector<int> a;
for (int i = 0; i < n; i++) {
num[i] = good[i] = 0;
sz[i] = 1;
root[i] = i;
compv[i].push_back(i);
}
for (int i = n - 1; i >= 0; i--) {
a = add(i);
for (const auto &v : a) {
// connect v, i
int x = root[i], y = root[v];
if (x == y) continue;
if (sz[x] > sz[y]) swap(x, y);
for (const auto &u : compv[x]) {
root[u] = y;
num[u] += sz[y];
compv[y].push_back(u);
}
sz[y] += sz[x];
compv[x].clear();
}
}
for (int i = 0; i < n; i++)
denum[num[i]] = i;
for (int i = 0; i < n; i++) compv[i].clear();
// numerated. now ranges
for (int i = 0; i < n; i++) {
good[i] = 0;
sz[i] = 1;
root[i] = i;
compv[i].push_back(i);
ranges[i].push_back({ n, num[i], num[i] });
roots[i].emplace_back(n, i);
}
for (int i = n - 1; i >= 0; i--) {
a = add(i);
for (const auto &v : a) {
int x = root[i], y = root[v];
if (x == y) continue;
if (sz[x] > sz[y]) swap(x, y);
for (const auto &u : compv[x]) {
root[u] = y;
compv[y].push_back(u);
roots[u].emplace_back(i, y);
}
sz[y] += sz[x];
compv[x].clear();
ranges[y].push_back({ i, min(ranges[x].back()[1], ranges[y].back()[1]), max(ranges[x].back()[2], ranges[y].back()[2]) });
}
}
}
pair<int, int> getrange(int time, int v) {
int lo, hi, mid;
lo = 0, hi = (int)roots[v].size() - 1;
while (lo < hi) {
mid = (lo + hi + 1) / 2;
if (roots[v][mid].first >= time) lo = mid;
else hi = mid - 1;
}
v = roots[v][lo].second;
lo = 0, hi = (int)ranges[v].size() - 1;
while (lo < hi) {
mid = (lo + hi + 1) / 2;
if (ranges[v][mid][0] >= time) lo = mid;
else hi = mid - 1;
}
return{ ranges[v][lo][1], ranges[v][lo][2] };
}
struct query {
int l, r, s, e, ind;
query() {}
query(int ll, int rr, int ss, int ee, int ii) : l(ll), r(rr), s(ss), e(ee), ind(ii) {}
bool operator < (const query &a) const {
return r < a.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;
for (int i = 0; i < X.size(); i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
numerate();
if (OO) {
/*
cout << "numerated: ";
for (int i = 0; i < n; i++) cout << num[i] << " "; cout << '\n';
while (1) {
cout << "L, v: ";
int tim, v;
cin >> tim >> v;
pair<int, int> tmp = getrange(tim, v);
cout << "[" << tmp.first << ", " << tmp.second << "]\n";
}
*/
}
for (int i = 0; i < n; i++) {
good[i] = 0;
sz[i] = 1;
root[i] = i;
comps[i].insert(num[i]);
}
vector<int> a;
int q = S.size();
vector<int> ans(q);
vector<query> Q(q);
for (int i = 0; i < q; i++)
Q[i] = query(L[i], R[i], S[i], E[i], i);
sort(Q.begin(), Q.end());
int nxt = 0;
for (const auto &i : Q) {
if (OO) {
cout << "processing query:\n";
cout << "(S, E, L, R) = " << i.s << " " << i.e << " " << i.l << " " << i.r << '\n';
}
while (nxt <= i.r) {
a = add(nxt);
if (OO) {
cout << nxt << " becomes good: ";
for (const auto &j : a) cout << j << " "; cout << '\n';
}
for (const auto &v : a) {
int x = root[nxt], y = root[v];
if (OO) cout << "merging " << nxt << " " << v << " = " << x << " " << y << '\n';
if (x == y) continue;
if (sz[x] > sz[y]) swap(x, y);
for (const auto &u : comps[x]) {
root[denum[u]] = y;
comps[y].insert(u);
}
sz[y] += sz[x];
comps[x].clear();
}
nxt++;
}
if (OO) {
cout << "roots: ";
for (int j = 0; j < n; j++) cout << root[j] << " "; cout << '\n';
}
pair<int, int> tmp = getrange(i.l, i.s);
auto it = comps[root[i.e]].lower_bound(tmp.first);
if (it == comps[root[i.e]].end() || tmp.second < *it) ans[i.ind] = 0;
else ans[i.ind] = 1;
}
return ans;
}
