#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second

int dst[(int)2e5 + 10];
vector <pair <int, int> > g[(int)2e5 + 10];
deque <int> q;

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) {
  int Q = S.size();
  int n = N;
  int m = X.size();
  std::vector<int> A(Q);
  for (int k = 0; k < Q; ++k) {
	  for (int i = 0; i < n; i++) {
		  g[i].clear();
		  dst[i] = (int)1e9 + 7;
	  }
	  for (int i = 0; i < m; i++) {
		  if ((X[i] < L[k] && Y[i] > R[k]) || (X[i] > R[k] && Y[i] < L[k])) {
			  continue;
		  }
		  if (X[i] >= L[k] && X[i] <= R[k] && Y[i] < L[k]) {
			  g[X[i]].push_back({Y[i], 1});
			  g[Y[i]].push_back({X[i], 0});
			  continue;
		  }
		  if (Y[i] >= L[k] && Y[i] <= R[k] && X[i] < L[k]) {
			  g[X[i]].push_back({Y[i], 0});
			  g[Y[i]].push_back({X[i], 1});
			  continue;
		  }
		  g[X[i]].push_back({Y[i], 0});
		  g[Y[i]].push_back({X[i], 0});
	  }
	  q.clear();
	  q.push_back(S[k]);
	  dst[S[k]] = 0;
	  while(q.size() > 0) {
		  int v = q.front();
		  q.pop_front();
		  // cout << v << '\n';
		  for (auto to: g[v]) {
			  if (dst[v] > 0 && to.ff > R[k]) continue;
			  // if (dst[v] > 0 && to.ff < L[k]) continue;
			  if (dst[to.ff] > dst[v] + to.ss) {
				  dst[to.ff] = dst[v] + to.ss;
				  if (to.ss == 0) {
				  	q.push_front(to.ff);
				  } else {
					 q.push_back(to.ff);
				  }
			  }
		  }
	  }
	  if (dst[E[k]] != (int)1e9 + 7) {
		  // cout << dst[E[k]] << '\n';
		  A[k] = 1;
	  } else {
		  A[k] = 0;
	  }
  }
  return A;
}