#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
int n, m, q;
vector<int> g[N];
vector<int> ans;
bitset<N> human, werewolf;
void dfs1(int u, int l) {
if(u < l) return;
human[u] = 1;
for(int v : g[u]) if(human[v] == 0)
dfs1(v, l);
}
void dfs2(int u, int r) {
if(r < u) return;
werewolf[u] = 1;
for(int v : g[u]) if(werewolf[v] == 0)
dfs2(v, r);
}
std::vector<int> check_validity(int _n, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
n = _n;
m = X.size();
q = S.size();
for(int i = 0; i < m; i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
for(int i = 0; i < q; i++) {
human = werewolf = 0;
dfs1(S[i], L[i]);
dfs2(E[i], R[i]);
if((human & werewolf) != 0)
ans.push_back(1);
else ans.push_back(0);
}
return ans;
}
