#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
#define ffor(i, a, b) for (ll i = a; i < b; i++)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()
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) {
int Q = S.size();
vpii edges, edges2, l, r;
rep(i, X.size()) {
if (X[i] > Y[i]) {
swap(X[i], Y[i]);
}
edges.emplace_back(X[i], Y[i]);
edges2.emplace_back(Y[i], X[i]);
}
sort(all(edges));
sort(all(edges2));
rep(i, Q) {
l.emplace_back(L[i], i);
r.emplace_back(R[i], i);
}
sort(all(l));
sort(all(r));
reverse(all(r));
vii res(Q);
vii parent(N, -1), parent2(N, -1);
function<int(int)> root, root2;
root = [&](int x) {
if (parent[x] < 0) {
return x;
}
return parent[x] = root(parent[x]);
};
root2 = [&](int x) {
if (parent2[x] < 0) {
return x;
}
return parent2[x] = root2(parent2[x]);
};
function<void(int, int)> merge, merge2;
merge = [&](int x, int y) {
int rx = root(x), ry = root(y);
if (rx != ry) {
if (parent[rx] < parent[ry]) {
swap(rx, ry);
}
parent[ry] += parent[rx];
parent[rx] = ry;
}
};
merge2 = [&](int x, int y) {
int rx = root2(x), ry = root2(y);
if (rx != ry) {
if (parent2[rx] < parent2[ry]) {
swap(rx, ry);
}
parent2[ry] += parent2[rx];
parent2[rx] = ry;
}
};
vvii reached(Q);
int edge_ind = edges.size() - 1;
while (!l.empty()) {
int i = l.back().second;
l.pop_back();
while (edge_ind >= 0 & edges[edge_ind].first >= L[i]) {
merge(edges[edge_ind].first, edges[edge_ind].second);
edge_ind--;
}
ffor(j, L[i], R[i] + 1) {
if (root(j) == root(S[i])) {
reached[i].emplace_back(j);
}
}
}
edge_ind = 0;
while (!r.empty()) {
int i = r.back().second;
r.pop_back();
while (edge_ind < edges2.size() && edges2[edge_ind].first <= R[i]) {
merge2(edges2[edge_ind].first, edges2[edge_ind].second);
edge_ind++;
}
forin(j, reached[i]) {
if (root2(j) == root2(E[i])) {
res[i] = 1;
break;
}
}
}
return res;
}
