#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int maxn = 3e3 + 2;
vector <int> ad [maxn];
bitset <maxn> vis1, vis2;
void dfs1 (int u, int l, int r) {
vis1[u] = 1;
for (int v: ad[u]) {
if (v < l || vis1[v]) continue;
dfs1(v, l, r);
}
}
int dfs2 (int u, int l, int r) {
vis2[u] = 1;
bool b = vis1[u];
for (int v: ad[u]) {
if (v > r || vis2[v]) continue;
b|=dfs2(v, l, r);
}
return b;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
for (int i = 0; i < N; i++){
ad[X[i]].push_back(Y[i]);
ad[Y[i]].push_back(X[i]);
}
int Q = S.size();
vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
vis1 = vis2 = 0;
dfs1(S[i], L[i], R[i]);
A[i] = dfs2(E[i], L[i], R[i]);
}
return A;
}
