#include<bits/stdc++.h>
//#include "werewolf.h"
using namespace std;
vector<vector<int>>adj(10000);
bool ok;
vector<bool>visited(10000,false);
void dfs (int s,int bot,int l,int r,int e,bool changed){
if (ok)return;
if (s==e){
ok=true;
return;
}
visited[s]=true;
for (auto x:adj[s]){
if (!visited[x]){
if (bot==0&&x>=r){
dfs(x,bot,l,r,e,changed);
}
else if (bot==1&&x<=l){
dfs(x,bot,l,r,e,changed);
}
else if (x>l&&x<r){
if (!changed)
dfs(x,bot^1,l,r,e,true);
dfs(x,bot,l,r,e,changed);
}
}
}
}
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) {
vector<int>A(E.size());
for (int i =0;i<N;++i){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
//0 - human
//1 - wolf
for (int i =0;i<E.size();++i){
ok=false;
for (int i =0;i<10000;++i)visited[i]=false;
dfs(s[i],0,L[i]-1,R[i],E[i],false);
A[i]|=ok;
}
return A;
}
