#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
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();
vector<int> A;
vector<int> adj[N+1];
int M = X.size();
for (int i=0; i<M; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
bool reach[N+1][2];
for (int i=0; i<Q; i++) {
int s = S[i], e = E[i], l = L[i], r = R[i];
memset(reach, 0, sizeof reach);
queue<pair<int, int>> proc;
if (s >= l) proc.push({s, 0});
while (!proc.empty()) {
auto x = proc.front();
proc.pop();
int no = x.first;
int st = x.second;
if (l <= no && no <= r && st == 0) {
if (!reach[no][1]) {
reach[no][1] = true;
proc.push({no, 1});
}
}
for (auto x: adj[no]) {
if (st == 0 && x < l) {
continue;
}
else if (st == 1 && x > r) {
continue;
}
else {
if (!reach[x][st]) {
reach[x][st] = true;
proc.push({x, st});
}
}
}
}
if (reach[e][1]) {
A.push_back(1);
}
else {
A.push_back(0);
}
}
return A;
}
