#include "werewolf.h"
#include <queue>
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();
std::vector<int> A(Q);
for (int i = 0; i < Q; ++i)
{
A[i] = 0;
}
int M = X.size();
std::vector<std::vector<int>> adj(N);
for (int i = 0; i < M; ++i)
{
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for (int qi = 0; qi < Q; ++qi)
{
int s = S[qi], e = E[qi];
int lo = L[qi], hi = R[qi];
std::vector<bool> visS(N, false);
std::queue<int> q1;
visS[s] = true, q1.push(s);
while (q1.size())
{
int u = q1.front();
q1.pop();
for (int v : adj[u])
if (!visS[v] && v >= lo)
visS[v] = true, q1.push(v);
}
std::vector<bool> visE(N, false);
std::queue<int> q2;
visE[e] = true, q2.push(e);
while (q2.size())
{
int u = q2.front();
q2.pop();
for (int v : adj[u])
if (!visE[v] && v <= hi)
visE[v] = true, q2.push(v);
}
bool ok = false;
for (int t = lo; t <= hi; ++t)
if (visS[t] && visE[t])
{
ok = true;
break;
}
A[qi] = ok;
}
return A;
}
