#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) {
int M = X.size();
int Q = S.size();
vector<vector<int>> adj(N);
for (int i = 0; i < M; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
vector<int> p(N);
function<int(int)> find = [&](int x) {
return x == p[x] ? x : p[x] = find(p[x]);
};
vector<vector<int>> s(N);
auto unite = [&](int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return;
}
if (s[x].size() > s[y].size()) {
swap(x, y);
}
for (int z : s[x]) {
p[z] = y;
s[y].push_back(z);
}
};
for (int i = 0; i < N; i++) {
p[i] = i;
s[i] = {i};
}
vector hi(N, vector<int>(N, -1));
for (int x = N - 1; x >= 0; x--) {
hi[x][x] = x;
for (int y : adj[x]) {
if (y < x || find(x) == find(y)) {
continue;
}
for (int u : s[find(x)]) {
for (int v : s[find(y)]) {
hi[u][v] = x;
hi[v][u] = x;
}
}
unite(x, y);
}
}
for (int i = 0; i < N; i++) {
p[i] = i;
s[i] = {i};
}
vector lo(N, vector<int>(N, -1));
for (int x = 0; x < N; x++) {
lo[x][x] = x;
for (int y : adj[x]) {
if (y > x || find(x) == find(y)) {
continue;
}
for (int u : s[find(x)]) {
for (int v : s[find(y)]) {
lo[u][v] = x;
lo[v][u] = x;
}
}
unite(x, y);
}
}
vector<int> ans(Q);
for (int i = 0; i < Q; i++) {
for (int j = L[i]; j <= R[i]; j++) {
if (hi[S[i]][j] >= L[i] && lo[j][E[i]] <= R[i]) {
ans[i] = 1;
}
}
}
return ans;
}
