#include "werewolf.h"
#include <queue>
#include <iostream>
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
VVI G;
const int INF = 1000000000;
bool found;
VVI vis;
void dfs(int form, int u, int dst, int left, int right) {
if (u == dst && form == 1) {
found = true;
return;
}
vis[form][u] = true;
for (int v : G[u]) {
if (form == 0) {
// soy humano
if (v < left) continue;
}
else {
// soy werewolf
if (v > right) continue;
}
if (!vis[form][v])
dfs(form, v, dst, left, right);
}
if (form == 0) {
if (left <= u && u <= right)
if (!vis[1][u])
dfs(1, u, dst, left, right);
}
}
bool solve(int N, int src, int dst, int left, int right) {
vis = VVI(2, VI(N, 0));
found = false;
dfs(0, src, dst, left, right);
return found;
}
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) {
G = VVI(N);
int M = X.size();
for (int j = 0; j < M; ++j) {
int u = X[j], v = Y[j];
G[u].push_back(v);
G[v].push_back(u);
}
int Q = S.size();
vector<int> res(Q);
for (int i = 0; i < Q; ++i) {
int src = S[i], dst = E[i];
int left = L[i], right = R[i];
res[i] = solve(N, src, dst, left, right);
}
return res;
}
