#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(int v, vector<vector<int>>& g, vector<int>& used, int l, int r) {
used[v] = 1;
for (auto u : g[v]) {
if (!used[u] && l <= u && u <= r)
dfs(u, g, used, l, 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) {
int m = X.size(), q = S.size();
vector<vector<int>> g(n);
for (int i = 0; i < m; i++)
g[X[i]].push_back(Y[i]), g[Y[i]].push_back(X[i]);
vector<int> u1(n), u2(n);
vector<int> ans(q, 0);
for (int i = 0; i < q; i++) {
fill(u1.begin(), u1.end(), 0); fill(u2.begin(), u2.end(), 0);
dfs(S[i], g, u1, L[i], n);
dfs(E[i], g, u2, 0, R[i]);
for (int v = 0; v < n; v++) {
if (u1[v] && u2[v]) {
ans[i] = 1;
break;
}
}
}
return ans;
}
