#include "werewolf.h"
#include <bits/stdc++.h>
#define MAX 10000000
using namespace std;
typedef vector<int> vi;
vector<vi> G;
vector<int> rw,rh,r;
map<int,int>m;
bool vish[200010],visw[200010],vis[200010];
int sw=0;
void dfslinealh(int i,int li){
if(r[i]<li) return;
if(vish[r[i]]==1) return;
rh.push_back(r[i]);
vish[r[i]]=1;
if(i==0 or i==r.size()-1) return;
dfslinealh(i-1,li);
dfslinealh(i+1,li);
}
void dfslinealw(int i,int ri){
if(r[i]>ri) return;
if(visw[r[i]]==1) return;
rw.push_back(r[i]);
visw[r[i]]=1;
if(i!=0)
dfslinealw(i-1,ri);
if(i!=r.size()-1)
dfslinealw(i+1,ri);
}
void armar_grafo(int u){
r.push_back(u);
vis[u]=1;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(vis[v]==0){
armar_grafo(v);
}
}
}
void dfsh(int u,int l){
if(u>=l){
rh.push_back(u);
vish[u]=1;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(vish[v]==false){
dfsh(v,l);
}
}
}
}
void dfsw(int u,int r){
if(u<=r){
rw.push_back(u);
if(vish[u]==1){
sw=1;
}
visw[u]=1;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(visw[v]==false){
dfsw(v,r);
}
}
}
}
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) {
bool plana=0;//plana=1;
G.resize(N+1);
std::vector<int> A;
for(int i=0;i<X.size();i++){
G[X[i]].push_back(Y[i]);
G[Y[i]].push_back(X[i]);
}
int id=-1;
for(int i=0;i<G.size();i++){
if(G[i].size()>2){
//plana=0;
break;
}
if(G[i].size()==1){
id=i;
}
}
if(plana==1){
/* armar_grafo(id);
map<int,int>m;
for(int j=0;j<r.size();j++){
m[r[j]]=j;
// cout<<r[j]<<" ";
}
//cout<<endl;
for(int i=0;i<S.size();i++){
memset(vish,0,sizeof vish);
memset(visw,0,sizeof visw);
rh.clear();
rw.clear();
dfslinealh(m[S[i]],L[i]);
dfslinealw(m[E[i]],R[i]);
sort(rh.begin(),rh.end());
bool sw=0;
for(int j=0;j<rw.size();j++){
if(binary_search(rh.begin(),rh.end(),rw[j])){
sw=1;
break;
}
}
if(sw==1){
A.push_back(1);
}
else{
A.push_back(0);
}
}*/
}
else{
for(int i=0;i<S.size();i++){
memset(vish,0,sizeof vish);
memset(visw,0,sizeof visw);
dfsh(S[i],L[i]);
sw=0;
dfsw(E[i],R[i]);
// if(plana==0){
for(int i=0;i<N;i++){
if(vish[i]==visw[i] and vish[i]==1){
sw=1;
break;
}
}
// }
if(sw==1){
A.push_back(1);
}
else{
A.push_back(0);
}
}
}
return A;
}
/*
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
int N = read_int();
int M = read_int();
int Q = read_int();
std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
for (int j = 0; j < M; ++j) {
X[j] = read_int();
Y[j] = read_int();
}
for (int i = 0; i < Q; ++i) {
S[i] = read_int();
E[i] = read_int();
L[i] = read_int();
R[i] = read_int();
}
std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
for (size_t i = 0; i < A.size(); ++i) {
printf("%d\n", A[i]);
}
return 0;
}*/
