#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int nmax = 2e5 + 5;
#define tree asdhgasdgjahsd
struct DSU {
vector<int> dsu;
vector<vector<int> > tree;
vector< vector<int> > p;
vector<int> pin, pout;
int inp = 0;
vector<int> preord;
bool cond;
void init(int n, bool c) {
dsu.resize(n);
pin.resize(n);
pout.resize(n);
tree.resize(n, vector<int>());
p.resize(n, vector<int>(18,0));
cond = c;
for(int i = 0; i < n; i++)
dsu[i] = i;
}
int father(int x) {
return (dsu[x] == x? x : father(dsu[x] = father(dsu[dsu[x]])));
}
void push(int u, int v) {
v = father(v);
if(v == u)
return;
p[v][0] = u;
tree[u].push_back(v);
dsu[v] = u;
}
void dfs(int node) {
preord.push_back(node);
pin[node] = inp++;
for(int i = 1; i < 18; ++i)
p[node][i] = p[p[node][i - 1]][i - 1];
for(auto x : tree[node])
dfs(x);
pout[node] = inp - 1;
}
int r;
vector<int> init(int root) {
p[root][0] = root;
dfs(root);
r = root;
return preord;
}
bool isanc(int f, int node) {
return pin[f] <= pin[node] && pout[node] <= pout[f];
}
pair<int,int> findbest(int start, int limit) {
for(int i = 17; i >= 0; i--) {
if(((p[start][i] < limit) ^ cond) || p[start][i] == limit)
start = p[start][i];
}
return {pin[start], pout[start]};
}
};
int n, m, q;
vector<int> g[nmax];
vector<int> v;
namespace AINT {
set<int> aint[nmax * 4];
void construct(int node = 1, int cl = 0, int cr = n - 1) {
if(cl == cr) {
aint[node].insert(v[cl]);
return;
}
int mid = cl + cr >> 1;
construct(2 * node, cl, mid);
construct(2 * node + 1, mid + 1, cr);
for(auto x : aint[2 * node])
aint[node].insert(x);
for(auto x : aint[2 * node + 1])
aint[node].insert(x);
return;
}
bool query(int l, int r, int liml, int limr, int node = 1, int cl = 0, int cr = n - 1) {
if(cr < l || r < cl)
return 0;
if(l <= cl && cr <= r) {
//cout <<"! " <<l <<' '<< cl << ' ' << cr << ' '<< r << '\t' << liml << ' ' << *aint[node].lower_bound(liml) <<' ' << limr << '\n';
auto it = aint[node].lower_bound(liml);
return (it != aint[node].end() &&(*it) <= limr);
}
int mid = cl + cr >> 1;
return query(l, r, liml, limr, 2 * node, cl, mid) ||
query(l, r, liml, limr, 2 * node + 1, mid + 1, cr);
}
};
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> s, std::vector<int> e,
std::vector<int> l, std::vector<int> r) {
n = N;
m = X.size();
q = l.size();
DSU lower;
DSU upper;
lower.init(n ,0);
upper.init(n ,1);
for(int i = 0; i < m; i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
for(int i = 0; i < n; i++) {
for(auto x : g[i])
if(x <= i)
lower.push(i, x);
}
for(int i = n - 1; i >= 0; i--) {
for(auto x : g[i])
if(x >= i)
upper.push(i, x);
}
vector<int> down = lower.init(n - 1), up = upper.init(0), inv(n);
v.resize(n);
for(int i = 0; i < n; i++) {
inv[up[i]] = i;
}
for(int i = 0; i < n; i++)
v[i] = inv[down[i]];
AINT::construct();
vector<int> sol(q, 0);
for(int i = 0, cl, cr, liml, limr; i < q; i++) {
swap(s[i], e[i]);
tie(cl, cr) = lower.findbest(s[i], r[i]);
tie(liml, limr) = upper.findbest(e[i], l[i]);
sol[i] = AINT::query(cl, cr, liml, limr);
}
return sol;
}
