#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 m = X.size(), q = S.size();
vector<vector<int>>g(n);
for(int i = 0; i < m; i++){
g[X[i]].emplace_back(i);
g[Y[i]].emplace_back(i);
}
vector<int>ans(q);
if(n <= 3000 && m <= 6000 && q <= 3000){
for(int i = 0; i < q; i++){
vector<vector<bool>>f(n, vector<bool>(2, false));
queue<pair<int, int>>q;
q.emplace(S[i], 0);
f[S[i]][0] = true;
while(!q.empty()){
auto [s, c] = q.front();
q.pop();
if(c == 0 && L[i] <= s && R[i] >= s){
f[s][1] = true;
q.emplace(s, 1);
}
for(int& j : g[s]){
int d = s ^ X[j] ^ Y[j];
if(((c == 0 & d >= L[i]) || (c == 1 && d <= R[i])) && !f[d][c]){
f[d][c] = true;
q.emplace(d, c);
}
}
}
ans[i] = f[E[i]][1];
}
}
return ans;
}
