#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> graph[200005];
bool visited[200005];
bool hvisited[200005];
bool result = false;
void humanspan(int u, int l)
{
hvisited[u] = true;
//cout << "hu " << u << '\n';
for(auto v: graph[u])
{
if(!hvisited[v] && v >= l)
{
humanspan(v, l);
}
}
}
void wolfspan(int u, int l, int r)
{
visited[u] = true;
//cout << "wu " << u << '\n';
for(auto v: graph[u])
{
if(!visited[v] && v <=r)
{
wolfspan(v, l, r);
}
}
}
int solve(int n, int s, int e, int l, int r)
{
result = false;
for(int i = 0; i < n; i ++)
{
visited[i] = false;
hvisited[i] = false;
}
humanspan(s, l);
wolfspan(e, l, r);
for(int i = l; i <=r; i ++)
{
if(visited[i] && hvisited[i])
{
return 1;
}
}
return 0;
}
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();
vector<int> A(Q, 0);
for(int i = 0; i < X.size(); i ++)
{
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
for(int i = 0; i < Q; i ++)
{
A[i] = solve(N, S[i], E[i], L[i], R[i]);
}
return A;
}
