#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
int n, m, q, c = 0;
vector<int> s, e, l, r, a;
vector<vector<int>>adj, v;
bool dfs(int u, int w = 0){
// cerr << u << " " << w << "\n";
if(u == e[c] && w) return true;
bool ans = false;
v[u][w] = 1;
for(int t : adj[u]){
if(!v[t][w]){
if(l[c] > t && !w) {
// cerr << t << " invalid " << w << "\n";
continue;
}
if(r[c] < t && w) {
// cerr << t << " invalid " << w << "\n";
continue;
}
if(l[c] <= t && r[c] >= t){
if(!w)
ans = ans || dfs(t, 0);
ans = ans || dfs(t, 1);
}
else
ans = ans || dfs(t, w);
}
}
return ans;
}
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();
adj = vector<vector<int>> (n);
for(int i = 0; i < m; i++){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
s = S, e = E, l = L, r = R;
a = vector<int> (q);
for(int i = 0; i < q; i++, c++){
v = vector<vector<int>>(n, vector<int> (2, 0));
if(s[i] >= l[i] && s[i] <= r[i])
a[i] = dfs(s[i]) || dfs(s[i], 1);
else
a[i] = dfs(s[i]);
}
return a;
}
