#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 3e2;
vector<int> g[MAXN];
void dfs(int v, int l, int r, vector<bool> &used){
used[v] = true;
for (int u : g[v]){
if (!used[u] && l <= u && u <= r){
dfs(u, l, r, used);
}
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int Q = S.size(), M = X.size();
vector<int> A(Q, 0);
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++){
vector<bool> used1(N, false), used2(N, false);
dfs(S[i], L[i], N - 1, used1);
dfs(E[i], 0, R[i], used2);
for (int j = L[i]; j <= R[i]; j++){
if (used1[j] && used2[j]) A[i] = 1;
}
}
return A;
}
/**
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
