#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
struct city {
vi con;
bool visited_normal=false;
bool visited_werewolf=false;
};
vector<city> cities;
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
int Q = S.size();
int M = X.size();
cities.resize(N);
for(int m=0; m<M; m++) {
cities[X[m]].con.push_back(Y[m]);
cities[Y[m]].con.push_back(X[m]);
}
vi A(Q,0);
for (int i = 0; i < Q; ++i) {
/*if(S[i]<L[i] or E[i]>R[i]) { //impossible
//A[i] = 0;
continue;
}*/
queue<pair<int,bool>> bfs;
bfs.push({S[i],false});
while(!bfs.empty()) {
int c;
bool ww;
tie(c,ww)=bfs.front();
bfs.pop();
if(c==E[i]) {
A[i]=1;
break;
}
if(ww and cities[c].visited_werewolf) continue;
if(!ww and cities[c].visited_normal) continue;
bool transform=false;
if(!ww and c<=R[i] and !cities[c].visited_werewolf) transform=true;
if(!ww) cities[c].visited_normal=true;
if(ww or transform) cities[c].visited_werewolf=true;
for(int other:cities[c].con) {
if(!ww and other>=L[i] and !cities[other].visited_normal) bfs.push({other,false});
if((ww or transform) and other<=R[i] and !cities[other].visited_werewolf) bfs.push({other,true});
}
}
for(int n=0; n<N; n++) cities[n].visited_normal=cities[n].visited_werewolf=false;
//A[i] = 0;
}
return A;
}
