#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MX=6000;
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
bitset<MX> visited[2];
vi adj[MX];
int M = X.size();
RE(i,M) {
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
int Q = S.size();
vi A(Q);
RE(i,Q) {
RE(j,2) visited[j].reset();
queue<ii> q; q.push({S[i],0}); visited[0][S[i]]=1;
while(!q.empty()) {
ii p = q.front(); q.pop();
int u = p.fi;
int w = p.se;
for(int v : adj[u]) {
if(visited[w][v] ) continue;
if(!w && v < L[i]) continue;
if( w && v > R[i]) continue;
visited[w][v] = 1;
q.push({v,w});
}
if(!visited[1][u] && L[i] <= u && u <= R[i]) {
visited[1][u] = 1;
q.push({u,1});
}
}
A[i] = visited[1][E[i]];
}
return A;
}
