#include "werewolf.h"
#include <bits/stdc++.h>
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 Q = S.size();
vector<int> A(Q);
vector<vector<int>> adj(N);
for(int i = 0; i < X.size(); i++){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for(int i = 0; i < Q; i++){
int low = L[i]; int high = R[i];
int start = S[i]; int end = E[i];
queue<vector<int>> q;
q.push({start, start <= low}); //u, transform state: 0 = human, 1 = can be both, 2 = wolf: Impossible to go back from 2
vector<int> visited(N);
bool isPossible = false;
while(!q.empty()){
int u = q.front()[0]; int state = q.front()[1];
q.pop();
if(u == end && (state == 2 || state == 1)){
isPossible = true;
break;
}
if(visited[u]) continue;
visited[u] = 1;
for(auto v : adj[u]){
if(v > high){
if(state == 2) continue;
q.push({v, 0});
}else if(v < low){
if(state == 0) continue;
q.push({v, 2});
}else{
q.push({v, 1});
}
}
}
A[i] = isPossible;
}
return A;
}
// 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
// #include "grader.cpp"
