#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
using ll = long long;
using vi = vector<ll>;
#define pb push_back
const int mxN = 3005;
vi adj[mxN];
bool vis1[mxN];
bool vis2[mxN];
void dfs1(int x, int l) {
vis1[x] = true;
for(auto y : adj[x]) {
if(!vis1[y] && y >= l) {
dfs1(y, l);
}
}
}
void dfs2(int x, int r) {
vis2[x] = true;
for(auto y : adj[x] ){
if(!vis2[y] && y <= r) {
dfs2(y, r);
}
}
}
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 Q = S.size();
vector<int> A(Q);
for(int i = 0; i < (int) X.size(); ++i) {
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
for(int i = 0; i < Q; ++i) {
memset(vis1, false, sizeof(vis1));
memset(vis2, false, sizeof(vis2));
dfs1(S[i], L[i]);
dfs2(E[i], R[i]);
bool pos = false;
for(int j = L[i]; j <= R[i]; ++j) {
if(vis1[j] && vis2[j]) {
pos = true;
break;
}
}
A[i] = (pos ? 1 : 0);
}
return A;
}
