#include "werewolf.h"
#include "iostream"
#include "array"
#include "queue"
#ifndef EVAL
#include "grader.cpp"
#endif
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 m = X.size();
vector<vector<int>> e(n);
for (int i = 0; i < m; i++) {
e[X[i]].push_back(Y[i]);
e[Y[i]].push_back(X[i]);
}
int Q = S.size();
vector<int> ans(Q);
for (int i = 0; i < Q; i++) {
vector<array<int, 2>> dp(n);
queue<array<int, 2>> q;
q.push({S[i], 0});
dp[S[i]][0] = 1;
while (!q.empty()) {
auto [u, p] = q.front();
q.pop();
if (L[i] <= u && u <= R[i] && p == 0 && !dp[u][1]) {
dp[u][1] = 1;
q.push({u, 1});
}
for (int v : e[u]) {
if (!dp[v][p] && ((p == 0 && v >= L[i]) || (p == 1 && v <= R[i]))) {
dp[v][p] = 1;
q.push({v, p});
}
}
}
ans[i] = dp[E[i]][1];
}
return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
