#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int maxn5 = 3e3 + 10;
const int lg = 20;
vector <int> adj[maxn5], ret;
bool mark[maxn5], mark2[maxn5];
int liml, limr, n;
void dfs(int v){
mark[v] = true;
for(auto u : adj[v]) if(u >= liml && u <= limr && !mark[u])
dfs(u);
}
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) {
n = N;
int q = s.size();
int m = x.size();
for(int i = 0; i < m; i++){
adj[x[i]].pb(y[i]);
adj[y[i]].pb(x[i]);
}
for(int i = 0; i < q; i++){
liml = 0, limr = r[i];
memset(mark, false, sizeof mark);
dfs(e[i]);
for(int j = 0; j < n; j++)
mark2[j] = mark[j];
memset(mark, false, sizeof mark);
liml = l[i]; limr = n;
dfs(s[i]);
bool re = false;
for(int j = 0; j < n; j++)
re |= (mark[j] && mark2[j]);
ret.pb(re);
}
return ret;
}
