#include "werewolf.h"
#include <bits/stdc++.h>
struct UnionFind {
int n;
std::vector<int> data;
UnionFind(int n_) : n(n_) {
data.assign(n, -1);
}
int find(int v) {
if (data[v] < 0) return v;
else return data[v] = find(data[v]);
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (data[a] > data[b]) std::swap(a, b);
data[a] += data[b];
data[b] = a;
}
};
constexpr int B = 3;
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) {
const int M = (int)X.size();
const int Q = (int)S.size();
std::vector<int> answer(Q);
std::vector<std::vector<int>> graph(2 * N);
for (int i = 0; i < M; ++i) {
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
std::vector<char> isSeen(2 * N);
for (int i = 0; i < Q; ++i) {
std::fill(isSeen.begin(), isSeen.end(), false);
std::queue<int> que;
que.push(S[i]);
while (not que.empty()) {
const int f = que.front();
que.pop();
if (f < N) {
if (L[i] <= f and f <= R[i]) {
if (not isSeen[f + N]) {
isSeen[f + N] = true;
que.push(f + N);
}
}
}
const int u = f >= N ? f - N : f;
for (const int t : graph[u]) {
if (f >= N) {
if (t <= R[i]) {
if (not isSeen[t + N]) {
isSeen[t + N] = true;
que.push(t + N);
}
}
} else {
if (t >= L[i]) {
if (not isSeen[t]) {
isSeen[t] = true;
que.push(t);
}
}
}
}
}
answer[i] = isSeen[E[i] + N];
}
return answer;
}
