#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
typedef long long ll;
int n, m, q;
vector<int> ans;
vector<int> link[3002];
int visited[3002];
void dfs1(int x, int lim){
visited[x] |= 1;
for(auto y: link[x]){
if(visited[y] & 1) continue;
if(y < lim) continue;
dfs1(y, lim);
}
}
void dfs2(int x, int lim){
visited[x] |= 2;
for(auto y: link[x]){
if(visited[y] & 2) continue;
if(y > lim) continue;
dfs2(y, lim);
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
n = N, m = (int)X.size(), q = (int)L.size();
ans.resize(q);
for(int i=0; i<m; i++){
link[X[i]].push_back(Y[i]);
link[Y[i]].push_back(X[i]);
}
for(int i=0; i<q; i++){
memset(visited, 0, sizeof(visited));
dfs1(S[i], L[i]);
dfs2(E[i], R[i]);
int smth = 0;
for(int j=0; j<n; j++) smth = max(smth, visited[j]);
ans[i] = (smth == 3);
}
return ans;
}
