#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=3000+5;
int n,q,x[mxn],y[mxn],a[mxn],b[mxn],color[mxn],color2[mxn];
vector<int>vt[mxn];
void dfs(int u,int l,int r){
if(u<l||u>r) return;
color[u]=1;
for(int v:vt[u]){
if(!color[v]&&v>=l&&v<=r){
dfs(v,l,r);
}
}
}
void dfs2(int u,int l,int r){
if(u<l||u>r) return;
color2[u]=1;
for(int v:vt[u]){
if(!color2[v]&&v>=l&&v<=r){
dfs2(v,l,r);
}
}
}
vector<int> check_validity(int N,vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
n=N;
q=S.size();
for(int i=0;i<X.size();i++){
vt[X[i]+1].pb(Y[i]+1);
vt[Y[i]+1].pb(X[i]+1);
}
for(int i=0;i<S.size();i++){
x[i+1]=S[i]+1;
y[i+1]=E[i]+1;
a[i+1]=L[i]+1;
b[i+1]=R[i]+1;
}
vector<int>ans;
for(int i=1;i<=q;i++){
memset(color,0,sizeof(color));
memset(color2,0,sizeof(color2));
dfs(x[i],a[i],n);
dfs2(y[i],1,b[i]);
int ok=0;
for(int j=a[i];j<=b[i];j++){
if(color[j]&&color2[j]){
ok=1;
break;
}
}
if(ok){
ans.pb(1);
}
else{
ans.pb(0);
}
}
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
*/
