#include "werewolf.h"
#include <cstring>
using namespace std;
using vi = vector<int>;
#define sz(x) (int)x.size()
const int MAXN = 2e5;
vi G[MAXN];
bool vis[MAXN], can;
int s, e, l, r;
void DFS(int u, int d, int t, bool& flag) {
if(u == d) flag = true;
vis[u] = true;
for(int v : G[u]) {
if(!vis[v]) {
if(t == 0){
if(v >= l) DFS(v, d, t, flag);
} else {
if(v <= r) DFS(v, d, t, flag);
}
}
}
}
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
for(int i=0; i<sz(X); i++) {
int u = X[i], v = Y[i];
G[u].push_back(v);
G[v].push_back(u);
}
int Q = sz(S);
vi ret(Q);
for(int i=0; i<Q; i++) {
s = S[i]; e = E[i]; l = L[i]; r = R[i];
can = false;
for(int i=0; i<N; i++) {
if(i > r) continue;
bool flag = false;
memset(vis, false, sizeof(vis));
DFS(s, i, 0, flag);
if(flag) {
flag = false;
memset(vis, false, sizeof(vis));
DFS(i, e, 1, flag);
if(flag) { can = true; break; }
}
}
ret[i] = (can)? 1 : 0;
}
return ret;
}
