#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> ans(Q);
for (int i = 0; i < Q; i++) {
if (S[i] < L[i] || R[i] < E[i]) {
continue;
}
vector<int> hi(N, -1);
priority_queue<pair<int, int>> p;
p.emplace(S[i], S[i]);
while (!p.empty()) {
auto [v, x] = p.top();
p.pop();
if (hi[x] != -1) {
continue;
}
hi[x] = v;
for (int y : adj[x]) {
p.emplace(min(v, y), y);
}
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
for (int j = L[i]; j <= R[i]; j++) {
if (hi[j] >= L[i]) {
q.emplace(j, j);
}
}
vector<int> lo(N, N);
while (!q.empty()) {
auto [v, x] = q.top();
q.pop();
if (lo[x] != N) {
continue;
}
lo[x] = v;
for (int y : adj[x]) {
q.emplace(max(v, y), y);
}
}
if (lo[E[i]] <= R[i]) {
ans[i] = 1;
}
}
return ans;
}
