#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
vector<vector<int>> G(N);
assert(X.size() == Y.size());
int M = X.size();
for (int i = 0; i < M; i++) {
G[X[i]].push_back(Y[i]);
G[Y[i]].push_back(X[i]);
}
vector<int> p(N), we(N, -1), siz(N, 1);
iota(p.begin(), p.end(), 0);
for (int i = N - 1; i >= 0; i--) {
for (int u : G[i]) {
if (u < i)
continue;
int v = i;
while (u != p[u])
u = p[u];
while (v != p[v])
v = p[v];
if (u == v)
continue;
if (siz[u] > siz[v])
swap(u, v);
p[u] = v;
we[u] = i;
siz[v] += siz[u];
}
}
vector<map<int, int>> s(N);
for (int i = 0; i < N; i++) {
int v = i;
s[i][v] = i;
while (v != p[v]) {
s[i][p[v]] = we[v];
v = p[v];
}
}
vector<vector<tuple<int, int, int, int>>> qu(N);
int Q = L.size();
assert(R.size() == Q && S.size() == Q && E.size() == Q);
for (int i = 0; i < Q; i++)
qu[R[i]].push_back({E[i], S[i], L[i], i});
vector<int> np(N), A(Q);
iota(np.begin(), np.end(), 0);
for (int i = 0; i < N; i++) {
for (int u : G[i]) {
if (u > i)
continue;
int v = i;
while (u != np[u])
u = np[u];
while (v != np[v])
v = np[v];
if (u == v)
continue;
if (s[u].size() > s[v].size())
swap(u, v);
np[u] = v;
for (auto [x, c] : s[u])
s[v][x] = max(s[v][x], c);
}
for (auto [u, v, l, idx] : qu[i]) {
while (u != np[u])
u = np[u];
while (we[v] >= l)
v = p[v];
A[idx] = s[u][v] >= l;
}
}
return A;
}
