#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int Nx = 200000;
vector<int> gr[Nx+5];
/*
struct node{
int x;
bool form; // 0 human 1 werewolf
node(){}
node(int _x,bool _form){
x = _x;
form = _form;
}
};*/
int e,l,r;
bool vis[Nx+5][3];
bool pre[Nx+5][3];
bool dfs(int node,bool form){
if(node == e && form){
return 1;
}
if(form && node > r)return 0;
if(!form && node < l)return 0;
bool &ans = pre[node][form];
if(vis[node][form])return ans;
vis[node][form] = 1;
for(auto u:gr[node]){
if(form && u <= r){
ans = ans || dfs(u,1);
}else if(!form){
if(u >= l)ans = ans || dfs(u,0);
if(u >= l && u <= r) ans = ans || dfs(u,1);
if(ans)return ans;
if(node >= l && node <= r && u <= r)ans = ans || dfs(u,1);
}
if(ans)return ans;
}
return ans;
}
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();
int M = X.size();
vector<int> ans(Q,0);
for(int i=0;i<M;i++){
gr[X[i]].push_back(Y[i]);
gr[Y[i]].push_back(X[i]);
}
for(int i=0;i<Q;i++){
memset(vis,0,sizeof vis);
memset(pre,0,sizeof pre);
e = E[i], l = L[i], r = R[i];
ans[i] = dfs(S[i],0);
}
return ans;
}
/*
run werewolf 03.in 03.out
*/
