#include "werewolf.h"
#include <queue>
#include <iostream>
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(), Q = S.size();
vector<int> A(Q);
if (N <= 3000 && M <= 6000 && Q <= 3000) { // subtasks 1 and 2
vector<vector<int>> g(N);
for (int i = 0; i < M; ++i) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
for (int qq = 0; qq < Q; ++qq) {
cerr << " ON QUERY " << qq << endl;
int s = S[qq], e = E[qq], l = L[qq], r = R[qq];
// bfs from start as human
cerr << " BFS FROM S" << endl;
vector<bool> canHuman(N);
queue<int> q;
q.push(s), canHuman[s] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int y : g[x]) {
if (!canHuman[y] && y >= l) q.push(y), canHuman[y] = true;
}
}
cerr << " BFS FROM E" << endl;
vector<bool> canWolf(N);
q.push(e), canWolf[e] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int y : g[x]) {
if (!canWolf[y] && y <= r) q.push(y), canWolf[y] = true;
}
}
for (int i = 0; i < N; ++i) {
if (canHuman[i] && canWolf[i] && l <= i && i <= r) A[qq] = 1;
}
}
}
return A;
}
