#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
int n, m, q;
const int N = 2e5 + 10;
vector<int> g[N];
vector<int> cnt;
vector<bool> us;
void dfs(int s, int l, int r) {
us[s] = 1;
cnt[s]++;
for(int to : g[s]) {
if(us[to] || to > r || to < l) continue;
dfs(to, l, r);
}
}
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)S.size();
vector<int> res(q);
for(int i = 0; i < m; i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
if(n <= 3000 && q <= 3000) {
for(int i = 0; i < q; i++) {
cnt.assign(n, 0);
us.assign(n, false);
dfs(S[i], L[i], n - 1);
us.assign(n, false);
dfs(E[i], 0, R[i]);
if(*max_element(cnt.begin(), cnt.end()) > 1)
res[i] = 1;
}
}
for(int i = 0; i < n; i++) {
g[i].clear();
}
return res;
}
