#include "werewolf.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "grader.cpp"
#endif // LOCAL
#define pb push_back
using namespace std;
const int N = 2e5 + 10;
int canh[N], canw[N];
vector<int> a[N];
void dfs_l(int u, int num){
canw[u] = 1;
for(auto v : a[u])
if(canw[v] == 0 && v <= num)
dfs_l(v, num);
}
void dfs_g(int u, int num){
canh[u] = 1;
for(auto v : a[u])
if(canh[v] == 0 && v >= num)
dfs_g(v, num);
}
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;
ans.resize(q);
for(int i = 0; i < m; ++i){
a[x[i]].pb(y[i]);
a[y[i]].pb(x[i]);
}
for(int i = 0; i < q; ++i){
for(int j = 0; j < n; ++j)
canh[j] = canw[j] = 0;
dfs_g(s[i], l[i]);
dfs_l(e[i], r[i]);
bool f = false;
for(int j = l[i]; j <= r[i]; ++j)
f |= (canh[j] && canw[j]);
ans[i] = f;
}
return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
