#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
void dfsHuman(int u, int N, vector<vector<int>> &adj, vector<bool> &humanReach, int curL) {
if (humanReach[u] || u < curL) return;
humanReach[u] = true;
for (int v: adj[u]) {
dfsHuman(v,N,adj,humanReach,curL);
}
}
void dfsWolf(int u, int N, vector<vector<int>> &adj, vector<bool> &wolfReach, int curR) {
if (wolfReach[u] || u > curR) return;
wolfReach[u] = true;
for (int v: adj[u]) {
dfsWolf(v,N,adj,wolfReach,curR);
}
}
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();
vector<vector<int>> adj(N);
for (int i = 0; i < N; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
vector<int> A(Q);
for (int q = 0; q < Q; q++) {
//S[q],E[q],L[q],R[q]
vector<bool> humanReach(N,false), wolfReach(N,false);
dfsHuman(S[q],N,adj,humanReach,L[q]);
dfsWolf(E[q],N,adj,wolfReach,R[q]);
bool connected = false;
for (int i = 0; i < N; i++) {
if (humanReach[i] && wolfReach[i]) connected = true;
}
A[q] = connected;
}
return A;
}
