#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
int n, m, q;
vector< pair<int, int> > g[2][N];
int l, r;
int vis[2][N];
void dfs(int u, int werewolf) {
if((!werewolf && u < l) || (werewolf && r < u)) return;
vis[werewolf][u] = 1;
for(auto e : g[werewolf][u]) if(!vis[e.first][e.second]) {
if(!werewolf && e.first)
if(r < u) continue;
dfs(e.second, e.first);
}
}
vector<int> ans;
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[0][X[i]].push_back({0, Y[i]});
g[0][Y[i]].push_back({0, X[i]});
g[0][X[i]].push_back({1, Y[i]});
g[0][Y[i]].push_back({1, X[i]});
g[1][X[i]].push_back({1, Y[i]});
g[1][Y[i]].push_back({1, X[i]});
}
for(int i = 0; i < q; i++) {
for(int u = 0; u < n; u++)
vis[0][u] = vis[1][u] = 0;
l = L[i], r = R[i];
dfs(S[i], 0);
if(vis[1][E[i]]) ans.push_back(1);
else ans.push_back(0);
}
return ans;
}
